The smallest singular value of a random rectangular matrix

By Mark Rudelson, Roman Vershynin. 2008

397 citations recorded by the source corpus.

We prove an optimal estimate on the smallest singular value of a random subgaussian matrix, valid for all fixed dimensions. For an N by n matrix A with independent and identically distributed subgaussian entries, the smallest singular value of A is at least of the order \sqrt{N} - \sqrt{n-1} with high probability. A sharp estimate on the probability is also obtained.

Subfields: Applied Mathematics, Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/5bcb1fcf2004b6994e7a8068aa2aead8a55596fd

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 Discrete Mathematics and Combinatorics

In Statistics and Probability

Citations in the corpus

Invertibility of Sparse non-Hermitian matrices (2015, background): “Generalizing this idea, when the coordinates of the vector x are real, a notion termed as least common denominator (lcd) was introduced in [21, 23], to capture the additive structure in x.”
Sample covariance matrices of heavy-tailed distributions (2016, result): “lassical works [33] and [3] regarding almost sure convergence of appropriately normalized singular values when the coordinates of the underlying distributions are i.i.d.; as well as more recent works [22, 14, 18, 25, 9, 1, 2, 29, 19, 26, 20, 17, 28, 11, 10, 31, 32, 21, 27, 8]. For a more comprehensi”
Singularity of random Bernoulli matrices (2018, positive): “It was proved in [13] that for any unit vector x, P {∣∣∑ i aijxi ∣∣ ≤ t } ≤ Ct+ C LCD(x) + e −cn for any t > 0 (see also [14]).”
Tight Sample Complexity of Large-Margin Learning (2010, background): “In the following Theorem we generalize results of Rudelson and Vershynin to encompass also non-identically distributed coordinates.”
The Power of Linear Reconstruction Attacks (2012, background): “The remaining6 boolean functions of two variables are degenerate.”
Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution (2022, positive): “For the lower bound we use a result from Rudelson & Vershynin (2009) (see page 4, in the equation below Equation 1.11), since Z ∈ Rn×m is a matrix with each entry sampled from N (0, 1), we get for all t > 0: P(σmin(Z) ≤ √ n− √ m− t) ≤ e−t2/2 (A.155) With a bit of algebra, this gives us that with…”
Concentration inequalities for random tensors (2019, neutral): “For d = 1, this problem has been extensively studied in random matrix theory [16, 31, 23, 32, 25, 3, 26, 34, 27, 13, 10, 35, 36].”
Sparse Matrix Factorization (2013, background): “For a random ± 1 matrix X , it is known [12,14] that with high probability of 1 − ǫ the smallest and largest singular values are at least ǫ/ √ n and at most O ( √ n ).”
Independence test for high dimensional data based on regularized canonical correlation coefficients (2015, background): “Under Assumptions 2-4, from Silverstein and Bai (1995) and Pan (2010), my2t(z) is the unique solution in C+ to my2t(z) = mHt ( z − 1 1 + y2my2t(z) ) , (2.”
Minimax risks for sparse regressions: Ultra-high-dimensional phenomenons (2010, neutral): “Rudelson and Vershynin [41] have provided a control similar to (11.”
Small Ball Probabilities for Linear Images of High-Dimensional Distributions (2014, neutral): “44 92 v1 [ m at h. PR ] 1 8 Fe b 20 14 0.9 r(A), where r(A) denotes the stable rank of A.”
Spectral norm of products of random and deterministic matrices (2008, methodology): “5) for all dimensions was obtained in [27].”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, background): “Rudelson and Vershynin [RV09] cite this result and comment that it can be turned into a concentration inequality of the following form: p Taking t = √ m yields the result with probability exponentially close to 1.”
Random matrices: tail bounds for gaps between eigenvalues (2015, methodology): “First of all, we will introduce the extension of LCD to higher dimension, following Rudelson and Vershynin (see [26]).”