Bounding the smallest singular value of a random matrix without concentration

Abstract

Given $X$ a random vector in ${\mathbb{R}}^n$, set $X_1,...,X_N$ to be independent copies of $X$ and let $Γ=\frac{1}{\sqrt{N}}\sum_{i=1}^N <X_i,\cdot>e_i$ be the matrix whose rows are $\frac{X_1}{\sqrt{N}},\dots, \frac{X_N}{\sqrt{N}}$. We obtain sharp probabilistic lower bounds on the smallest singular value $λ_{\min}(Γ)$ in a rather general situation, and in particular, under the assumption that $X$ is an isotropic random vector for which $\sup_{t\in S^{n-1}}{\mathbb{E}}|<t,X>|^{2+η} \leq L$ for some $L,η>0$. Our results imply that a Bai-Yin type lower bound holds for $η>2$, and, up to a log-factor, for $η=2$ as well. The bounds hold without any additional assumptions on the Euclidean norm $\|X\|_{\ell_2^n}$. Moreover, we establish a nontrivial lower bound even without any higher moment assumptions (corresponding to the case $η=0$), if the linear forms satisfy a weak `small ball' property.