PaperlayerView exact revision on arXiv

Source-linked AI summary

Invertibility of symmetric random matrices

Roman Vershynin

arXiv:1102.0300v4math.PRmath.FA

TL;DR

For symmetric random matrices, even proving that singularity probability tends to zero is difficult. This paper uses decoupling and regularized LCD methods to address invertibility, establishing compressible-vector invertibility with exponentially high probability and resolving the incompressible-vector distance problem.

  • Problem

    For symmetric random matrices, the invertibility problem asks how small the singularity probability is; even showing it tends to zero is difficult.

    Source: §1.1 · pp. 2–3

  • Method

    The proof decouples quadratic forms into bilinear forms and uses regularized LCD to address additive structure amid decoupling and conditioning losses.

    Source: §1.4 · pp. 9–10

  • Results

    The argument establishes invertibility for compressible vectors with probability at least 1 − 2e^-cn and resolves the incompressible-vector distance problem, completing Theorem 1.1.

    Source: §1.4 · pp. 8, 11

  • Takeaways & Limitations

    Regularized LCD targets the most unstructured part of a vector of a given size, the paper’s response to losses in decoupling and conditioning.

    Source: §1.4 · p. 10

    The singularity-probability exponent is not optimal: the argument’s decoupling losses prevent this technique from reaching the optimal exponent 1.

    Source: §1.2 · p. 6

Abstract

from arXiv · show

We study n by n symmetric random matrices H, possibly discrete, with iid above-diagonal entries. We show that H is singular with probability at most exp(-n^c), and the spectral norm of the inverse of H is O(sqrt{n}). Furthermore, the spectrum of H is delocalized on the optimal scale o(n^{-1/2}). These results improve upon a polynomial singularity bound due to Costello, Tao and Vu, and they generalize, up to constant factors, results of Tao and Vu, and Erdos, Schlein and Yau.

1 Introduction

The section develops invertibility results for symmetric random matrices, including bounds on singularity and inverse norm and eigenvalue delocalization at the o(n^-1/2) scale. Its argument uses a structure theorem to bound regularized LCD and concentration of quadratic forms to address the distance problem for incompressible vectors.

1.1 Invertibility problem

  • The invertibility problem asks for the singularity probability and typical inverse norm; for symmetric Bernoulli matrices, Costello, Tao and Vu showed that singularity probability tends to zero.The paper frames this as difficult even to establish for symmetric Bernoulli matrices, whose on- and above-diagonal entries are independent symmetric ±1 variables.Source: §1.1 · pp. 2–3

1.3 Four moments

  • With only finite fourth moments, the four-moment result removes the spectral-norm condition at weaker probability bounds and yields asymptotic nonsingularity, resolvent and inverse-norm bounds, and eigenvalue delocalization.These conclusions hold under the fourth-moment assumption; the probability bound is weaker than in the subgaussian result.Source: §1.3 · pp. 6–7

1.4 Overview of the argument

  • For compressible vectors, a covering argument and an independent-entry minor reduce the symmetric-matrix invertibility problem to a lower bound for one vector, yielding good invertibility with probability at least 1 − 2e^-cn.The proof partitions the sphere into compressible and incompressible vectors and treats the two classes separately.Source: §1.4 · pp. 7–8
  • For incompressible vectors, the proof reduces invertibility to concentration of quadratic forms, decouples them into bilinear forms, and uses regularized LCD to control additive structure and concentration.The regularized LCD captures an unstructured part of a vector while allowing vectors with small regularized LCD to be controlled through metric entropy.Source: §1.4 · pp. 9–10
  • Concentration of quadratic forms yields a solution to the distance problem and completes the incompressible-vector part of the invertibility proof.The overview points to Theorem 8.1 and Corollary 9.1 for these steps and says they complete Theorem 1.1.Source: §1.4 · p. 11
  • The proof combines individual Littlewood-Offord bounds with low metric entropy, covering and a union bound to exclude vectors mapping to a fixed vector.It conditions on an independent vector and uses a net over the relevant level set.Source: §1.4 · pp. 11–12
  • With exponentially high probability, the structure theorem gives bD(x, λ) ≳ (λn)^2/λ.The overview identifies this as essentially the statement of structure theorem (1.20).Source: §1.4 · p. 12

2 Notation and initial reductions of the problem

This section fixes notation, recalls spectral-norm estimates, and reduces the main argument to symmetric matrices with iid above-diagonal entries and finite fourth moment.

2.1 Notation

  • The paper uses positive constants that may vary between occurrences, depend on natural parameters, and never depend on the dimension n.The diagonal entries are arbitrary fixed numbers, while the above-diagonal entries are iid and have finite fourth moment.Source: §2.1 · p. 12, §2.3 · p. 15
  • For a subset I, x_I denotes the restriction of x to I, while P_Ix is its projection into R^n with zeros outside I.The section also fixes notation for the Euclidean and sup norms, unit sphere and ball, distances, eigenvalues, and matrix norms.Source: §2.1 · p. 13

2.2 Nets and bounds on the spectral norm

  • An ε-net covers a compact set within distance ε, and its minimal size is the covering number; net bounds are used alongside spectral-norm estimates.The section recalls a subgaussian spectral-norm estimate and notes that a similar bound under fourth-moment assumptions holds only in expectation.Source: §2.2 · pp. 13–14

2.3 Initial reductions of the problem

  • The initial reductions work with symmetric matrices whose above-diagonal entries are iid with finite fourth moment and whose diagonal entries are fixed.A small continuous perturbation is used to assume general position and avoid technicalities from degenerate cases.Source: §2.3 · p. 15

3 Preliminaries: small ball probabilities, compressible and incompressible vectors

The preliminaries provide small-ball tools and split the unit sphere into compressible and incompressible vectors, reducing invertibility to separate bounds on those two classes.

3.1 Small ball probabilities, L´evy concentration function

  • The L´evy concentration function controls the probability that a random vector falls in a Euclidean ball, and tensorization transfers scalar small-ball bounds to vectors.For sums of independent unit-variance variables with bounded fourth moments, the section recalls a general, explicitly weak concentration bound.Source: §3.1 · p. 16

3.2 Compressible and incompressible vectors

  • Compressible vectors lie within distance c1 of vectors supported on at most c0n coordinates; incompressible vectors are the remaining unit vectors.Compressible vectors have small covering numbers, while incompressible vectors have a proportional number of coordinates with magnitudes of order n^-1/2.Source: §3.2 · pp. 17–18

3.3 Invertibility for incompressible vectors via the distance problem

  • The unit sphere splits into these two classes, so invertibility can be established by treating compressible and incompressible vectors separately.For incompressible vectors, the reduction is to bounding the probability that a random column lies close to the span of the other columns.Source: §3.2 · p. 18, §3.3 · pp. 18–19

4 Invertibility for compressible vectors

The section establishes invertibility bounds for compressible vectors, first for a fixed vector and then uniformly over the class using approximation.

4 Invertibility for compressible vectors

  • A uniform lower-bound result for ∥Ax∥2 on compressible vectors solves the first part of the invertibility problem.The stated result is for matrices satisfying (A), with constants depending on K and the fourth-moment parameter M4.Source: §4 · p. 19, §4.2 · pp. 21–22

4.1 Small ball probabilities for Ax

  • For every fixed unit vector x, Proposition 4.1 gives a small-ball probability bound for Ax under assumption (A).Its constant c4.1 depends only on M4.Source: §4.1 · p. 19

4.2 Small ball probabilities for Ax uniformly over compressible

  • An approximation argument extends the fixed-vector estimate to a uniform invertibility bound over compressible vectors.The proof uses a net of the compressible class and applies the fixed-vector estimate over the net.Source: §4.2 · pp. 20–22

5 Distance problem via small ball probabilities for quadratic forms

For incompressible vectors, the distance problem connects column-to-span distances with small-ball probabilities for quadratic forms.

5 Distance problem via small ball probabilities for quadratic forms

  • The incompressible-vector problem reduces to bounding the probability that a column is close to the span of the other columns.The section identifies this as a distance problem for a random vector and a random hyperplane.Source: §5 · p. 22
  • The distance problem is reduced to small-ball probabilities for quadratic forms, including forms of the type ⟨B^-1X, X⟩.Here B is the minor obtained by removing the first row and column, and X is the first column with its first entry removed.Source: §5 · pp. 22–23

6 Small ball probabilities for quadratic forms via additive structure

The section develops Littlewood–Offord small-ball bounds by using coefficient vectors’ additive structure, measured through LCD, and extends this approach to quadratic forms and random vectors.

6 Small ball probabilities for quadratic forms via additive structure

  • Decoupling reduces quadratic-form small-ball estimates to linear-form estimates that account for the additive structure of their coefficients.The target forms are ⟨A^-1X, X⟩; the section introduces the linear theory as a basis for extending it to quadratic forms.Source: §6 · p. 24, §6.2 · p. 27

6.1 Small ball probabilities via LCD

  • The general concentration bound can remain a fixed probability even as the interval shrinks, so sharper estimates must use coefficient-vector structure.For independent random signs, the sum ±1 ± 1 equals zero with probability 1/2.Source: §6.1 · p. 24
  • LCD measures coefficient-vector structure; for rational coordinates, it corresponds to the least common denominator, or the smallest θ such that θx is integer-valued.The paper extends this concept to real vectors and adopts a particular form proposed by M. Rudelson.Source: §6.1 · p. 24
  • Theorem 6.3 bounds linear-sum concentration using LCD under iid assumptions that bound each variable’s concentration and first absolute moment.Its proof uses Esseen’s lemma and conditioning; the supplied theorem passage does not show the bound’s formula.Source: §6.1 · pp. 25–26

6.2 Regularized LCD

  • Regularized LCD is designed to measure structure in the least structured part of an incompressible vector’s coefficients.The definition is applied to vectors in Incomp(c0, c1).Source: §6.2 · p. 28
  • Proposition 6.9 gives a small-ball bound via regularized LCD for iid variables satisfying concentration and first-moment assumptions.The proposition’s formula is not included in the supplied passage.Source: §6.2 · p. 29

6.3 Small ball probabilities for Ax via regularized LCD

  • Proposition 6.11 bounds small-ball probabilities for Ax using regularized LCD when A satisfies the paper’s matrix assumptions and x is incompressible.The argument exploits independent entries in a submatrix and tensorizes coordinate-level bounds.Source: §6.3 · pp. 30–31

7 Estimating additive structure

The section shows that A^-1u has large regularized LCD with high probability for fixed u, using covering estimates for low-LCD vectors to turn fixed-vector small-ball bounds into uniform control.

7 Estimating additive structure

  • For fixed u, the normalized vector A^-1u is incompressible and has large regularized LCD with high probability.The structure theorem’s constants depend on the matrix parameters K and M4.Source: §7 · p. 31

7.1 Covering sets of vectors with small LCD

  • The covering proposition constructs nets for regularized-LCD sublevel sets whose cardinality is substantially smaller than the trivial sphere-net bound.The stated improvement comes from a factor involving (λn)^c7.4 in the net-size estimate.Source: §7.1 · p. 32

7.2 Proof of Structure Theorem 7.1.

  • The proof of the structure theorem combines fixed-vector small-ball estimates on LCD sublevel sets with covering nets to obtain uniform control.The proof applies Lemma 7.9 to sublevel sets and uses a union bound over a net.Source: §7.2 · pp. 37–38

8 Small ball probabilities for quadratic forms

Under the stated independence and moment assumptions, the section bounds the Lévy concentration of a self-normalized quadratic form using denominator control and decoupling into a linear form for Littlewood–Offord analysis. An optimization fact yields an inequality valid for all ε and completes Theorem 8.1.

8 Small ball probabilities for quadratic forms

  • C8.1ε^1/9 + 2exp(−n^c8.1) + P(E_K^c) bounds the Lévy concentration function for every ε ≥ 0, with constants depending only on K and M4.Theorem 8.1 assumes A satisfies (A), while X is independent of A with independent, identically distributed entries of mean zero, unit variance, and bounded fourth moment.Source: §8 · p. 40

8.1 Size of A−1X

  • Structure Theorem 7.1 and a union bound give regularized-LCD bounds for the vectors x_k, which are then used with Littlewood–Offord estimates to control coordinates of A^−1X.The proof combines the coordinate estimates using a lemma for sums of dependent nonnegative random variables.Source: §8.1 · pp. 42–43
  • With probability at least 1 − e^(−c′n), ∥A^−1X∥2 is at least c′/(3K), providing a lower bound used to control the denominator.The bound follows when E_K holds and uses a high-probability lower bound on ∥X∥2.Source: §8.1 · pp. 41–42

8.2 Decoupling quadratic forms

  • Decoupling replaces the quadratic form’s concentration problem, after conditioning on coordinates outside J, with that of a linear form estimated by Littlewood–Offord theory.The resulting vector and shift are fixed under this conditioning.Source: §8.2 · pp. 43–44

8.3 Proof of Theorem 8.1

  • A random coordinate split J and an assignment spread(x) are chosen so the regularity condition holds on spread(x) for incompressible vectors.The assignment depends on J and is used in the regularized-LCD estimates.Source: §8.3 · p. 45
  • Proposition 8.2 controls the denominator for both X and a scaled difference of independent copies, enabling the proof to handle decoupling losses.The argument packages these controls into a good event involving A, X, X′, and J.Source: §8.3 · pp. 45–46
  • Conditioning on the coordinates outside J fixes the decoupling vector, reducing the remaining estimate to independent summands bounded using Proposition 6.9 and the regularized-LCD condition.The proof applies the decoupling lemma before estimating the resulting linear-form concentration.Source: §8.3 · pp. 47–48
  • ε0 = ε^1/2/λ^1/8 optimizes the bound, and λ ≥ n^−c7.1 makes the polynomial term dominate the exponentially small term.The proof then obtains its final estimate by simplifying the optimized bound.Source: §8.3 · p. 49
  • Fact 8.6 assumes p(ε) ≤ M^a ε^b + n^-c′M for all ε ∈ [0, 1] and C ≤ M ≤ n^c.Source: §8.3 · p. 49
  • Choosing M0 within the allowed range yields the assumed inequality for ε ≥ n^-c′M0/b.Source: §8.3 · p. 49
  • Using M = n^c gives the inequality over the complementary range ε ≤ n^-100ac.Source: §8.3 · p. 49
  • Taking M0 minimally so that c′M0/b ≥ 100ac makes the two ranges cover every ε ≥ 0.The proof concludes with C0 = M^a.Source: §8.3 · p. 49
  • The optimization fact is applied with a = 5/32, b = 1/8, and M = 1/λ.The resulting inequality holds on [0, 1], and the proof extends it to ε > 1.Source: §8.3 · p. 49
  • Theorem 8.1 is completed by applying the optimized inequality for every ε ≥ 0.The inequality also holds for ε > 1 because its right-hand side is then larger than 1.Source: §8.3 · p. 49

9 Consequences: the distance problem and invertibility of random matrices

The section derives a distance bound between a random vector and a subspace, then uses distance estimates to prove invertibility for symmetric random matrices.

9.1 The distance theorem

  • Corollary 9.1 gives a bound on the distance between a column of a random matrix and the span of its other columns.The corollary applies to matrices satisfying assumption (A).Source: §9.1 · p. 50

9.2 Invertibility of random matrices: proof of Theorem 1.1.

  • Theorem 9.2 establishes an invertibility bound for random matrices satisfying (A), with constants depending on the fourth-moment bound and K.The proof identifies this bound as the result that implies Theorem 1.1.Source: §9.2 · pp. 50–51
  • The invertibility proof splits vectors into compressible and incompressible cases, bounding the former directly and handling the latter through column-to-span distances.The compressible-vector probability is bounded by 2e^-c4.2n; the incompressible-vector probability is estimated via distances.Source: §9.2 · p. 51
Loading 1102.0300v4…