Sharp gap between volume sampling and the worst matrix with a prescribed spectrum
For $n \ge 3$, $\lambda \in (0,\infty)^n$ and $V \in O(n)$ let $K_V = V^{\mathsf T} \operatorname{diag}(\lambda)\, V$, and for $I \subseteq \{1, \dots, n\}$ write $K_{:I}$, $K_{I:}$ and $K_{II}$ for the columns, the rows and the principal submatrix of $K$ indexed by $I$. For $1 \le k \le n - 1$ let $$x_k(\lambda) = \max_{V \in O(n)} \, \min_{|I| = k} \operatorname{tr}\bigl(K_V - (K_V)_{:I} (K_V)_{II}^{-1} (K_V)_{I:}\bigr), \qquad y_k(\lambda) = \frac{(k+1)\, e_{k+1}(\lambda)}{e_k(\lambda)},$$ where $e_j$ is the $j$-th elementary symmetric polynomial. Thus $x_k(\lambda)$ is the least trace error of a Nyström approximation from $k$ columns, for the worst eigenbasis. If $I$ is drawn with probability $\det((K_V)_{II})/e_k(\lambda)$ (volume sampling), the expected trace error is $y_k(\lambda)$ for every $V$ (Deshpande, Rademacher, Vempala and Wang; Guruswami and Sinop). Amsel et al. ask for tightness bounds between $x_k(\lambda)$ and $y_k(\lambda)$, and note that $x_{n-1}(\lambda) = y_{n-1}(\lambda)$ for every $\lambda$, by the Schur–Horn theorem.
Problem. For $1 \le k \le n - 2$ let $$R_{n,k} = \sup_{\lambda \in (0,\infty)^n} \frac{y_k(\lambda)}{x_k(\lambda)}.$$ Determine, up to universal multiplicative constants, how $R_{n,k}$ depends on $n$ and $k$, for all $n \ge 3$ and $1 \le k \le n - 2$.
Source: Stated by OpenProblemsInNLA, after Amsel et al. (2026), Problem 4.7, which asks for tightness bounds between x_k(λ) and y_k(λ).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CO, PR
- Keywords
- column subset selection, Nyström approximations, OpenProblemsInNLA, volume sampling
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{amsel2026,
author = {Amsel, Noah and Baumann, Yves and Beckman, Paul and B{\"u}rgisser, Peter and Cama{\~n}o, Chris and Chen, Tyler and Chow, Edmond and Damle, Anil and Derezinski, Michal and Embree, Mark and Epperly, Ethan N. and Falgout, Robert and Fornace, Mark and Greenbaum, Anne and Greif, Chen and Halikias, Diana and Huang, Zhen and Jarlebring, Elias and Koutis, Yiannis and Kressner, Daniel and Kyng, Rasmus and Liesen, J{\"o}rg and Lok, Jackie and Meyer, Raphael A. and Nakatsukasa, Yuji and Pearce, Kate and Peng, Richard and Persson, David and Rebrova, Eliza and Schneider, Ryan and Shah, Rikhav and Solomonik, Edgar and Srivastava, Nikhil and Townsend, Alex and Webber, Robert J. and Williams, Jess},
title = {Linear Systems and Eigenvalue Problems: Open Questions from a {S}imons Workshop},
year = {2026},
eprint = {2602.05394},
archivePrefix = {arXiv},
}
@inproceedings{guruswami2012,
author = {Guruswami, Venkatesan and Sinop, Ali Kemal},
title = {Optimal column-based low-rank matrix reconstruction},
booktitle = {Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)},
publisher = {SIAM},
year = {2012},
pages = {1207--1214},
doi = {10.1137/1.9781611973099.95},
eprint = {1104.1732},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-tr03,
author = {Townsend, Alex},
title = {{TR-03}: Sharp gap between volume sampling and the worst matrix with a prescribed spectrum},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/TR-03/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Resolution claims
For the real isospectral Nyström minimax problem, an oversampled limiting-profile estimate is proved and used to obtain an upper bound for every positive finite spectrum: $R_{n,k}\le\min\{k+1,n-k,C\sqrt{k}\}$ for $2\le k\le n-2$, with the explicit universal constant $C=2^{34}e^{2560}$. The argument completes the conditional upper-bound reduction in the author's preceding research package. Its main ingredients are a clipping inequality, rectangular Gaussian inverse-trace small-ball …
For $n\ge3$ and a positive spectrum $\lambda$, let $x_1(\lambda)$ be the largest, over orthogonal $V$, of the least trace error of a one-column Nyström approximation of $K_V=V^{\mathsf T}\operatorname{diag}(\lambda)V$, and let $y_1(\lambda)=2e_2(\lambda)/e_1(\lambda)$. The note proves $x_1(\lambda)=y_1(\lambda)=\sum_j\lambda_j-\sum_j\lambda_j^2/\sum_j\lambda_j$ for every positive spectrum, so $R_{n,1}=1$ for every $n\ge3$. The upper bound averages the column errors with weights $K_{ii}/\operatorname{tr}K$. The matching construction uses the lemma …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-09 | Open → Partially resolved | The registry's curators | The one-column spectral minimax identity v1 recorded from OpenProblemsInNLA @ eb7c9d6, holden-tr03-2026-09-12/one-column.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00179, "Sharp gap between volume sampling and the worst matrix with a prescribed spectrum", clopen.solutions.