The least singular value of a random square matrix is O(n−1/2)

By Mark Rudelson, Roman Vershynin. 2008

65 citations recorded by the source corpus.

Abstract Let A be a matrix whose entries are real i.i.d. centered random variables with unit variance and suitable moment assumptions. Then the smallest singular value s n ( A ) is of order n − 1 / 2 with high probability. The lower estimate of this type was proved recently by the authors; in this Note we establish the matching upper estimate. To cite this article: M. Rudelson, R. Vershynin, C. R. Acad. Sci. Paris, Ser. I 346 (2008).

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/10b6e8196cfc8e2b470104b0a86008836d93d26b

How researchers see this paper

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

In Discrete Mathematics and Combinatorics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Random Matrices: the Distribution of the Smallest Singular Values (2009, methodology): “)), σ 1(M n(ξ)) = (2+o(1)) √ n. UNIVERSALITY AT THE HARD EDGE 27 One can prove this lemma by combining [5, Theorem 5.8] with the tools in Appendix F or by following the arguments in [1, 17]. See also [35, 37] for references. Corollary 6.10. Let ξ ij be R- or C-normalized, independent random variable”
Invertibility of Sparse non-Hermitian matrices (2015, background): “Finally a matching upper bound was proved for sub-Gaussian entries in [22], and improved under finite fourth moment assumption in [31].”
Non-asymptotic theory of random matrices: extreme singular values (2010, background): “Both these bounds, upper and lower, hold with high probability under the weaker fourth moment assumption on the entries [65, 66].”
Introduction to the non-asymptotic analysis of random matrices (2010, background): “For square random matrices (N = n) one has the optimal bound smin(A) ∼ n−1/2 with high probability [67, 68].”
Spectral norm of products of random and deterministic matrices (2008, background): “We obtain P { max j=1,...,n Sj > 2(np+ log(2n))s } ≤ ne−c log(2n)s = 2−csn1−cs. Integration yields E max j=1,...,n Sj ≤ C(np+ log(2n)).”
Lower bounds for the smallest singular value of structured random matrices (2016, unknown): “MR2407948 (2010g:60048) [30] Rudelson, M.”