The smallest singular value of products of random combinatorial and deterministic matrices
In the authors' words
Let be fixed, and let be positive integers satisfying . Let be an random combinatorial matrix whose rows are independent and uniformly distributed over the vectors in having exactly ones. For an arbitrary deterministic invertible matrix , we establish two-sided bounds for the smallest singular value of . More precisely, for every , \[ \mathbb P\!\left( \varepsilon\le s_n(Q_nM)\cdot \|M^{-1}\|_{HS} \le \varepsilon^{-2} \right) \ge 1-C\left( \varepsilon+d^{-1/2}+e^{-c \operatorname{sr}(M^{-1})} \right)-2e^{-cn}, \] where positive constants depend only on and denotes the stable rank. Consequently, for any sequence of deterministic invertible matrices satisfying , is typically of order . In particular, taking recovers the known scale for .
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.