Sharp row-deletion singular-value limit for spherical random matrices
Fix $0 < \theta < 1$. For $A \in \mathbb{R}^{m \times n}$ let $$s_\theta(A) = \min_{S \subseteq \{1, \dots, m\},\ |S| = \lfloor \theta m \rfloor} \ \min_{\|x\|_2 = 1} \|A_S x\|_2,$$ where $A_S$ consists of the rows of $A$ indexed by $S$, and let $\|A\|_2$ be the spectral norm. Let $a_\theta > 0$ be defined by $\mathbb{P}(|G| \le a_\theta) = \theta$ for a standard normal $G$, and $$h_\theta = \frac{1}{\sqrt{2\pi}} \int_{-a_\theta}^{a_\theta} t^2 e^{-t^2/2}\,dt.$$ With $\theta = q - \beta$, the ratio $s_\theta(A)^2/\|A\|_2^2$ enters Steinerberger's sufficient condition for the $q$-quantile randomized Kaczmarz method to converge when a fraction $\beta$ of the equations is corrupted. For rows uniform on the sphere he suggested the limit below by a heuristic argument, keeping, for a fixed unit vector $x$, the rows with the smallest $|\langle a_i, x \rangle|$, which for large $n$ behave like $n^{-1/2}$ times standard normal variables; he asked whether it could be proved, and made quantitative in $m$, $n$ and $m/n$. Haddock, Needell, Rebrova and Swartworth proved, for a class of random matrices that includes those with independent rows uniform on the sphere, that with high probability every set of at least $\theta m$ rows of a sufficiently tall $A$ has smallest singular value at least a constant multiple of $\theta^{3/2}\sqrt{m/n}$.
Problem. Let $(m_j, n_j)$ be any sequence of dimensions with $n_j \to \infty$ and $m_j/n_j \to \infty$, and let $A_j \in \mathbb{R}^{m_j \times n_j}$ have independent rows, each uniformly distributed on the unit sphere $\mathbb{S}^{n_j - 1}$. Does $$\frac{s_\theta(A_j)^2}{\|A_j\|_2^2} \to h_\theta$$ in probability, for every such sequence?
Source: Steinerberger (2023), Section 2.3, the heuristic limit (8) and the question after it ((⋄) in arXiv:2107.05554v1), with θ = q − β; stated with ⌊θm⌋ rows and convergence in probability by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- Kaczmarz methods, OpenProblemsInNLA, random matrices, smallest singular values
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{steinerberger2023,
author = {Steinerberger, Stefan},
title = {Quantile-based random {K}aczmarz for corrupted linear systems of equations},
journal = {Inf. Inference},
volume = {12},
number = {1},
year = {2023},
pages = {448--465},
doi = {10.1093/imaiai/iaab029},
eprint = {2107.05554},
archivePrefix = {arXiv},
}
@article{haddock2022,
author = {Haddock, Jamie and Needell, Deanna and Rebrova, Elizaveta and Swartworth, William},
title = {Quantile-based iterative methods for corrupted systems of linear equations},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {43},
number = {2},
year = {2022},
pages = {605--637},
doi = {10.1137/21M1429187},
eprint = {2009.08089},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ie21,
author = {Townsend, Alex},
title = {{IE-21}: Sharp row-deletion singular-value limit for spherical random matrices},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-21/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For fixed $0 < \theta < 1$ and a real $m \times n$ matrix $A$ with unit rows, let $s_\theta(A)$ be the smallest singular value left after the worst choice of $\lfloor \theta m \rfloor$ of its rows. For independent rows uniform on $S^{n-1}$, the manuscript proves that $(n/m)\, s_\theta(A)^2$ and $s_\theta(A)^2/\|A\|_2^2$ converge in probability to the truncated Gaussian second …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 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-00225, "Sharp row-deletion singular-value limit for spherical random matrices", clopen.solutions.