Sharp sparsity threshold for injectivity of a random sparse rectangular matrix
Fix $c > 0$. Let $k$ run through the multiples of $100$, and for each $k$ let $n_k \ge k^{1+c}$ and $1 \le s_k \le k$ be integers. Let $M_k \in \mathbb{R}^{k \times n_k}$ have independent columns, each with exactly $s_k$ nonzero entries, in a uniformly random set of $s_k$ rows, equal to $\pm 1/\sqrt{s_k}$ with independent uniform signs. Independently of $M_k$, let $I_k$ be a uniformly random set of $k/100$ columns, write $(M_k)_{:I_k}$ for the $k \times k/100$ submatrix with those columns, and let $\sigma_{\min}(B) = \min_{\|x\|_2 = 1} \|Bx\|_2$. Huang, Rudelson and Tikhomirov proved that if $n_k/k \to \infty$, then for deterministic $k \times n_k$ matrices with boundedly many nonzero entries in each column, all of bounded size, and with only $o(n_k^2/k)$ pairs of columns whose supports share two or more rows, a uniformly random set of $\lfloor \varepsilon k \rfloor$ columns, for any fixed $\varepsilon > 0$, gives a submatrix with $\sigma_{\min} = o(1)$ with probability $1 - o(1)$.
Problem. Determine necessary and sufficient asymptotic conditions on $(s_k)$ for the existence of a constant $a > 0$, independent of $k$, such that $$\Pr\{\sigma_{\min}((M_k)_{:I_k}) \ge a\} = 1 - o(1) \quad (k \to \infty),$$ where the probability is over both $M_k$ and $I_k$.
Source: Huang, Rudelson and Tikhomirov (2026), Problem 7.2, which asks for the smallest singular value to be of order Ω(1) with high probability; in this form (probability 1 − o(1), k a multiple of 100, 1 ≤ s_k ≤ k), OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- PR — Probability
- Secondary
- NA
- Keywords
- OpenProblemsInNLA, smallest singular values, sparse random matrices, subspace injections
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{huang2026,
author = {Huang, Han and Rudelson, Mark and Tikhomirov, Konstantin},
title = {Well-invertible column subsets of sparse matrices are rare},
year = {2026},
eprint = {2607.05384},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-tr08,
author = {Townsend, Alex},
title = {{TR-08}: Sharp sparsity threshold for injectivity of a random sparse rectangular matrix},
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-08/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
Let $A_k$ have $k$ rows and $k/100$ independent columns. Each column has exactly $s_k$ uniformly located nonzero entries, with independent signs and magnitude $s_k^{-1/2}$. We prove the sequence criterion $$\exists a > 0:\ \Pr\{\sigma_{\min}(A_k) \ge a\} \longrightarrow 1 \quad\Longleftrightarrow\quad \liminf_{k \to \infty} \frac{s_k^2}{\log k} > 0.$$ Below this scale, a reservoir of columns supplies local cancellation trees. Above it, columns …
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-00209, "Sharp sparsity threshold for injectivity of a random sparse rectangular matrix", clopen.solutions.