Invertibility of random matrices: norm of the inverse

By Mark Rudelson. 2005

157 citations recorded by the source corpus.

Let A be an n × n matrix, whose entries are independent copies of a centered random variable satisfying the subgaussian tail estimate. We prove that the operator norm of A-1 does not exceed Cn3 / 2 with probability close to 1.

Subfields: Applied Mathematics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/3f41e1a4d7f304569029626d4cb77b13bbb2d2de

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 Mathematical Physics

In Statistics and Probability

Citations in the corpus

Concentration inequalities for random tensors (2019, unknown): “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].”
The circular law for random matrices (2007, methodology): “” We solve this problem using bounds for the minimal singular values of the matrices X(z) := X − zI based on techniques developed in Rudelson [17] and Rudelson and Vershynin [18].”
RANDOM MATRICES: THE CIRCULAR LAW (2007, background): “This assumption, unfortunately, excludes several important distributions, for instance discrete distributions such as Bernoulli random variables x ∈ {−1, +1}.”
Invertibility of Sparse non-Hermitian matrices (2015, background): “The idea of splitting the sphere into compressible (close to sparse) and incompressible ones originated in [16] and was further developed in [19, 21].”
No-gaps delocalization for general random matrices (2015, methodology): “We will also use a simple and useful tensorization property which goes back to [21, 23].”
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)).”
Smallest singular value of a random rectangular matrix (2009, unknown): “To estimate this characteristic function, we follow the conditioning argument of [20], [22].”
Non-asymptotic theory of random matrices: extreme singular values (2010, methodology): “The probability estimate of [62] can be further improved if one replaces the small ball probability bound of [63] with that of [65].”
Singularity of random Bernoulli matrices (2018, background): “Methods providing strong quantitative information on the smallest singular value of a random matrix were proposed in papers [12, 18].”
Random matrices: Universality of ESDs and the circular law (2008, result): “y from [26, Theorem 2.1] or [27, Theorem 4.1] and the Borel-Cantelli lemma, noting from (3) of Proposition 2.2 that the operator norm of M n is of polynomial size nO(1). There are previous results in [17], [24], [18], [25], which handled special cases with more assumptions on M n and the underlying ”
From the Littlewood-Offord problem to the Circular Law: universality of the spectral distribution of random matrices (2008, methodology): “Remark 5.6. Shortly after the appearance of [54], G¨ otze and Tikhomirov [22] gave an alternate proof of the Weak Circular Law with these hypotheses, using a variant of Theorem 4.7, which they obtained via a method from [ 37 ], [38].”
The Littlewood-Offord problem and invertibility of random matrices (2007, methodology): “mplicity, we state and prove all our results over the real ﬁeld. However, our arguments easily generalize to the complex ﬁeld; see e.g. [21]. 4. A weaker result was recently proved by the ﬁrst author [22] who showed that P s n(A) ≤ εn−3/2 ≤ Cε + Cn−1/2. He later improved the term n−1/2 to cn. Shortl”
Random Matrices: the Distribution of the Smallest Singular Values (2009, background): “A significant breakthrough was achieved by Rudelson [ Ru2 ], who established a polynomial lower bound for σn(Mn(ξ)) and also tail estimates for a certain range.”
The smallest singular value of a random rectangular matrix (2008, unknown): “S,ε √ m) ≤ Cm Z B(0, √ m) YN k=1 |φ(hθ,aki/ε)|dθ, where φ(t) = Eexp(2πitξ) is the characteristic function of ξ := ξ 1. To estimate this characteristic function, we follow the conditioning argument of [18], [20]. Let ξ′ be an independent copy of ξ and denote by ξ¯ the symmetric random variable ξ − ξ′”
Small Ball Probability, Inverse Theorems, and Applications (2012, methodology): “For t ≥ n−3/2, Rudelson in [44], making use of Halász’ machinery from [21], obtained a strong bound with an extra (multiplicative) constant factor.”
The smallest singular value of inhomogeneous square random matrices (2019, background): “The behavior of the smallest singular values of random matrices have been extensively studied [2, 4, 5, 11, 15, 16, 17, 20, 22, 24, 25, 26, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43].”