The smallest singular value of inhomogenous random rectangular matrices

Abstract

Let $A\in {\mathbb{R}}^{N\times n}$ ($N\ge n$) be a random matrix with with independent entries that have mean 0 variance 1 and bounded $2+{\hat{I}}^2$ moment. We show that the smallest singular value $\ddot{I}{ƒ}_n(A)$ satisfies \[ \Pr \left(σ_n(A) \leq \varepsilon(\sqrt{N+1} - \sqrt{n})\right) \leq (C\varepsilon)^{N-n+1} + e^{-cN}, \] for all $\epsilon >0$, where $c,C$ depend only on ${\hat{I}}^2$ and the $2+{\hat{I}}^2$ moment. This extends earlier results of Rudelson and Vershynin, who showed that such lower tail estimates held for rectangular matrices with i.i.d. mean 0 subgaussian entries. When the $2+{\hat{I}}^2$ moment assumption is replaced with a uniform anti-concentration assumption, ${\sup }_z\mathrm{Pr}\left(|X-z|<a\right)<b$, we show that \[ \Pr\left(σ_n(A) \leq \varepsilon(\sqrt{N+1} - \sqrt{n})\right) \leq (C\varepsilon\log(1/\varepsilon))^{N-n+1} + e^{-cN}, \] where $c,C$ now depend only on $a$ and $b$. This extends more recent work of Livshyts, whose showed that such lower tail estimates held for rectrangular matrices with i.i.d. rows. To prove these results we employ a number of new technical ingredients, including a new deviation inequality for the regularized Hilbert-Schmidt norm and a recently proven small ball estimate for the distance between a random vector and a subspace spanned by an inhomogeneous rectangular matrix.

introduced some new notation, simplified a number of proofs and fixed some typos and misprints. Updated Theorem 8 and 9 to be slightly more general