Well-invertible column subsets of sparse matrices are rare

Han Huang, Mark Rudelson, Konstantin Tikhomirov

A random $n\times k$ matrix $S$ is an \emph{$(r,\hat{I}\pm )$-oblivious subspace injection} (OSI) if $\mathbb{E}\Vert S^{\top }x{\Vert }_2^2=\Vert x{\Vert }_2^2$ for every $x\in {\mathbb{R}}^n$, and for every fixed…