{"id":"arxiv/2607.05384","url":"https://arxiv.org/abs/2607.05384","tags":["math.PR","math.FA"],"score":0,"title":"Well-invertible column subsets of sparse matrices are rare","domain":"math.PR","source":"arxiv","authors":["Han Huang","Mark Rudelson","Konstantin Tikhomirov"],"reviews":0,"subject":"math.PR","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-06","reactions":{}}