Well-invertible column subsets of sparse matrices are rare

Abstract

A random $n\times k$ matrix $S$ is an \emph{$(r,α)$-oblivious subspace injection} (OSI) if $\mathbb{E}\|S^\top x\|_2^2=\|x\|_2^2$ for every $x\in\mathbb{R}^n$, and for every fixed $r$-dimensional subspace $V\subset\mathbb{R}^n$, with probability close to one, one has $α\|x\|_2^2\le\|S^\top x\|_2^2$ for all $x\in V$. In this work, we show that in the regime $r=Ω(k)$ and $α=Ω(1)$, and under a mild additional structural assumption, no constant-row-sparsity matrix $S$ is OSI, thereby answering, in a strong form, a question raised by Camaño, Epperly, Meyer, and Tropp. We show that the failure of the OSI property for sparse random matrices stems from a general deterministic phenomenon, thereby reducing a probabilistic problem to a non-probabilistic one. This phenomenon is related to the restricted invertibility principle introduced in the seminal work of Bourgain--Tzafriri. Let $(n_k)_{k\in\mathbb{N}}$ be a sequence of integers satisfying $\frac{n_k}{k}\to\infty$. For each $k$, let $S^{(k)}$ be a $n_k\times k$ non-random matrix with $O(1)$ nonzero entries per row, whose nonzero entries have average magnitude $O(1)$, and such that the total number of pairs of rows with supports overlapping at two or more indices is $o({n_k}^2/k)$. We prove that for every constant $\varepsilon>0$, as $k\to\infty$, the overwhelming majority of $k\times \lfloor\varepsilon k\rfloor$ submatrices of $(S^{(k)})^\top$ have the smallest singular value $o(1)$. Thus, the well-invertible submatrices whose existence is guaranteed by the Bourgain--Tzafriri theorem are rare. The proof is itself based on probabilistic tools.

Disclosure

“the matrix theorem. Section 6 applies the result to SparseStack and OSI. We close with open problems. Funding acknowledgement. K.T. was partially supported by NSF grant DMS 2452120. Acknowledgement of AI Assistance. The authors used ChatGPT for language editing, stylistic suggestions, and assistance in developing and checking some proof arguments during the preparation of this manuscript. All mathematical statements, proofs, and final wording were independently reviewed and v”

PDF page 8

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-24T00:34:09.244Z

Structural counts