clopen.solutions
OP-00229 Solution claimed

Spectral-gap-independent constants for randomized block polynomial interpolation

Submit a result

Fix integers $b \ge 1$ and $d \ge 2$, and call diagonal matrices $\Lambda_1, \dots, \Lambda_d \in \mathbb{R}^{b \times b}$ with pairwise disjoint spectra admissible. Draw all entries of $\Omega_1, \dots, \Omega_d \in \mathbb{R}^{b \times b}$ independently from $N(0, 1)$, put $B_i = \Omega_i^{-1}\Lambda_i\Omega_i$, and let $a$ and $c$ be the smallest and largest diagonal entries of all the $\Lambda_i$. For each $k \in \{1, \dots, d\}$, relabel the triples $(B_i, \Lambda_i, \Omega_i)$ in the order $(k, 1, \dots, k-1, k+1, \dots, d)$, mark the relabelled matrices with a superscript $(k)$, and compute, for $i = d, d-1, \dots, 1$ in turn, $$S^{(k)}_{i,i} = I_b, \qquad S^{(k)}_{i,j} = B^{(k)}_i S^{(k)}_{i,j-1} - S^{(k)}_{i,j-1}\widehat B^{(k)}_j \quad (j = i+1, \dots, d),$$ $$\widehat\Omega^{(k)}_i = \Omega^{(k)}_i S^{(k)}_{i,d}, \qquad \widehat B^{(k)}_i = \bigl(\widehat\Omega^{(k)}_i\bigr)^{-1} \Lambda^{(k)}_i \widehat\Omega^{(k)}_i.$$ With spectral norms, let $$\chi^{(k)}_{\mathrm{mono}} = \max_{2 \le i \le d} \left\{ 1, \frac{\|aI - \widehat B^{(k)}_i\|_2}{\|aI - \Lambda^{(k)}_i\|_2}, \frac{\|cI - \widehat B^{(k)}_i\|_2}{\|cI - \Lambda^{(k)}_i\|_2} \right\},$$ where a ratio $0/0$ counts as $1$, $$\chi^{(k)}_{\mathrm{coef}} = \bigl\|(S^{(k)}_{1,d})^{-1}\bigr\|_2^{1/(d-1)} \min_{\substack{2 \le i \le d,\ \lambda \in \sigma(\Lambda^{(k)}_1) \\ \eta \in \sigma(\Lambda^{(k)}_i)}} |\lambda - \eta|,$$ $\chi_{\mathrm{mono}} = \max_k \chi^{(k)}_{\mathrm{mono}}$ and $\chi_{\mathrm{coef}} = \max_k \chi^{(k)}_{\mathrm{coef}}$; Shao showed that the inverses involved exist almost surely.

Shao introduced these quantities in an analysis of randomized small-block Lanczos: their product enters his bound on the fundamental matrix polynomials of block polynomial interpolation outside an interval containing the spectra. When $b = 1$, or when every $\Lambda_i$ is a multiple of the identity, $\chi_{\mathrm{mono}} = 1$ and $\chi_{\mathrm{coef}} \le 1$. Shao conjectured, with numerical evidence, that with high probability $\chi_{\mathrm{mono}}\chi_{\mathrm{coef}}$ is bounded by a constant depending on $b$ and $d$ but not on the $\Lambda_i$, nor on the eigenvalue gaps within and between them.

Problem. Is $\chi_{\mathrm{mono}}\chi_{\mathrm{coef}}$ uniformly bounded in probability over all admissible data, that is, for each $0 < \delta < 1$, is there a finite $C(b, d, \delta)$ such that $$\Pr\{\chi_{\mathrm{mono}}\chi_{\mathrm{coef}} \le C(b, d, \delta)\} \ge 1 - \delta$$ for every fixed admissible $(\Lambda_1, \dots, \Lambda_d)$? The constant must be independent of the eigenvalues and of all gaps within and between the blocks, and the probability is taken separately for each fixed input.

Source: Shao (2025), Conjecture 1 (Section 3.2 of arXiv:2507.10144v2), a with-high-probability bound by a constant depending only on b and d; made precise by OpenProblemsInNLA (the endpoints a and c taken as the extreme eigenvalues, as in Shao's own computations, a ratio 0/0 read as 1, and the bound as uniform boundedness in probability, the constant depending on the failure probability δ).

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary
NA — Numerical Analysis
Secondary
PR
Keywords
block Lanczos methods, matrix polynomials, OpenProblemsInNLA, random matrices
Literature checked
Oct. 8, 2026 by clemens-admin

References

@misc{shao2025,
  author        = {Shao, Nian},
  title         = {A structural bound for cluster robustness of randomized small-block {L}anczos},
  year          = {2025},
  eprint        = {2507.10144},
  archivePrefix = {arXiv},
  note          = {Theorem 1, equation (12) and Conjecture 1 of v2 (30 May 2026)},
}
@misc{openproblemsinnla-ke05,
  author       = {Townsend, Alex},
  title        = {{KE-05}: Spectral-gap-independent constants for randomized block polynomial interpolation},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/KE-05/README.md},
  note         = {Read at commit eb7c9d6, 2026-10-07},
}

Resolution claims

George Stepaniants

For block size $b = 2$ and $d = 3$ blocks, the manuscript gives deterministic diagonal data with pairwise disjoint spectra, $\Lambda_1 = 2I_2$, $\Lambda_2 = \operatorname{diag}(\varepsilon, 2\varepsilon)$ and $\Lambda_3 = \operatorname{diag}(0, 1)$, for which the random interpolation constant $\chi_{\mathrm{mono}}\chi_{\mathrm{coef}}$ from Shao's analysis of randomized small-block Lanczos is not bounded in probability uniformly in $\varepsilon$: along $\varepsilon_m = 1/(m+5)$, the …

Disproof · not verified · fidelity not established · posted on GitHub 12 Sep 2026

Status history

WhenChangeByReason
2026-10-08 Needs verification → Solution claimed clemens-admin Listed with the record of its solution, unreviewed.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00229, "Spectral-gap-independent constants for randomized block polynomial interpolation", clopen.solutions.