Optimal uniform row-deletion singular-value constant
Fix $0 < \theta < 1$. For a real $m \times n$ matrix $A$ whose rows $a_1, \dots, a_m$ all have Euclidean norm one, 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 exactly the rows indexed by $S$, and let $$M_{m,n}(\theta) = \sup_{\|a_1\|_2 = \dots = \|a_m\|_2 = 1} \sqrt{\frac{n}{m}}\, s_\theta(A),$$ the supremum over all such matrices. Let $a_\theta > 0$ be defined by $\mathbb{P}(|G| \le a_\theta) = \theta$ for a standard normal $G$, and $$c_\theta = \left(\frac{1}{\sqrt{2\pi}} \int_{-a_\theta}^{a_\theta} t^2 e^{-t^2/2}\,dt\right)^{1/2}.$$ With $\theta = q - \beta$, the ratio $s_\theta(A)^2/\|A\|_2^2$, where $\|A\|_2$ is the spectral norm, enters Steinerberger's sufficient condition for the $q$-quantile randomized Kaczmarz method to converge when a fraction $\beta$ of the equations is corrupted. For independent rows uniform on the sphere, he suggested by a heuristic argument that $s_\theta(A)^2/\|A\|_2^2 \to c_\theta^2$ as $n$ and $m/n$ tend to infinity (the problem of the sharp row-deletion singular-value limit for spherical random matrices). He asked whether every matrix with unit rows satisfies $s_\theta(A) \le (1 + o(1))\, c \sqrt{m/n}$ for a constant $c$, and whether the best such constant is the one his heuristic gives, $c_\theta$.
Problem. Determine the sharp asymptotic upper constant for $M_{m,n}(\theta)$ as $n \to \infty$ and $m/n \to \infty$. In particular, is it $c_\theta$: for every $\varepsilon > 0$, are there integers $N$ and $R$ such that $M_{m,n}(\theta) \le c_\theta + \varepsilon$ whenever $n \ge N$ and $m/n \ge R$, while no smaller constant has this property?
Source: Steinerberger (2023), Section 2.3, the third question after (8), with θ = q − β; made precise (the supremum M_{m,n}(θ), its quantifiers and ⌊θm⌋ rows) by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- corrupted linear systems, Kaczmarz methods, OpenProblemsInNLA, 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},
}
@misc{openproblemsinnla-ie22,
author = {Townsend, Alex},
title = {{IE-22}: Optimal uniform row-deletion singular-value constant},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-22/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-00226, "Optimal uniform row-deletion singular-value constant", clopen.solutions.