Bounding the smallest singular value of a random matrix without concentration

By Vladimir Koltchinskii, Shahar Mendelson. 2013

204 citations recorded by the source corpus.

Given $X$ a random vector in ${\mathbb{R}}^n$, set $X_1,...,X_N$ to be independent copies of $X$ and let $\Gamma=\frac{1}{\sqrt{N}}\sum_{i=1}^N 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 $\lambda_{\min}(\Gamma)$ 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}}| |^{2+\eta} \leq L$ for some $L,\eta>0$. Our results imply that a Bai-Yin type lower bound holds for $\eta>2$, and, up to a log-factor, for $\eta=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 $\eta=0$), if the linear forms satisfy a weak `small ball' property.

Subfields: Applied Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/463a62d2060a051da23db3dcaa57f185e583e7f0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Statistics and Probability

Citations in the corpus

Learning from MOM’s principles: Le Cam’s approach (2017, background): “We refer to Koltchinskii and Mendelson (2015); Lecu´e and Mendelson (2014); Mendelson (2015b, 2014b, 2015a); Rudelson and Vershynin (2014) for examples of distributions satisfying this assumption.”
Maximum likelihood estimation for linear Gaussian covariance models (2014, background): “Recently, there has also been work on deriving probabilistic finite-sample bounds for the smallest eigenvalue [KM15].”
Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices (2019, methodology): “This assumption is a strengthened variant of the “small ball” condition introduced by [39, 49, 41] in the analysis of sample covariance matrices and least squares regression, which amounts to assuming (2.”
Sample covariance matrices of heavy-tailed distributions (2016, background): “Note that better estimates for the smallest singular value were previously obtained in [17] and later strengthened in [31, 32].”
Slope meets Lasso: Improved oracle bounds and optimality (2016, background): “A useful sufficient condition for the s-sparse eigenvalue condition is the small ball condition [14, 19, 21].”
The smallest singular value of random rectangular matrices with no moment assumptions on entries (2014, background): “ndom matrices, an important question is whether any moment assumptions on entries are really necessary in order to get satisfactory lower estimates for the smallest singular value. Unlike in [17] and [5] where the matrix entries within a given row are not necessarily independent, in our paper we con”
On the Risk of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels (2019, background): “The approach proceeds along the lines of (Koltchinskii and Mendelson, 2015; Mendelson, 2014).”
Robust machine learning by median-of-means: Theory and practice (2017, methodology): “Note also that Assumption 3 is equivalent to the small ball property (cf. [46, 67]) which has been recently used in Learning theory and signal processing.”