pipette
ESEspañol

The smallest singular value of products of random combinatorial and deterministic matrices

Yuxiao Shi, Kexin Yu, Tingzhou Yu

Preprint

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 .

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.