clopen.solutions
OP-00226 Solution claimed

Optimal uniform row-deletion singular-value constant

Submit a result

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

Matthew J. Colbrook

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 …

Full resolution · not verified · fidelity not established · posted on GitHub 11 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-00226, "Optimal uniform row-deletion singular-value constant", clopen.solutions.