On the concentration of eigenvalues of random symmetric matrices

By Noga Alon, Michael Krivelevich, Van H. Vu. 2000

164 citations recorded by the source corpus.

It is shown that for every 1≤s≤n, the probability that thes-th largest eigenvalue of a random symmetricn-by-n matrix with independent random entries of absolute value at most 1 deviates from its median by more thant is at most 4e−t232s2. The main ingredient in the proof is Talagrand’s Inequality for concentration of measure in product spaces.

Subfields: Applied Mathematics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f13e1dabed4bc18f91cdf9ec961dbd39734e3a92

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

1. Joel A. Tropp
2. L. Erdős
3. Michael W. Mahoney
4. Horng-Tzer Yau
5. Alex Gittens
6. Jun Yin
7. Terence Tao
8. Van H. Vu

In Mathematical Physics

1. L. Erdős
2. Jun Yin
3. Horng-Tzer Yau
4. Terence Tao
5. Van H. Vu
6. Antti Knowles
7. Ji Oon Lee
8. Kevin Schnelli

In Statistics and Probability

1. L. Erdős
2. Horng-Tzer Yau
3. Jun Yin
4. Terence Tao
5. Van H. Vu
6. Michael W. Mahoney
7. Antti Knowles
8. Ji Oon Lee

Citations in the corpus

• Angular Synchronization by Eigenvectors and Semidefinite Programming (2009, unknown): “The largest eigenvalue of R , denoted λ1(R), is concentrated near the right edge of the support [2] and the universality of the edge of the spectrum [34] implies that it follows the Tracy–Widom distribution [36] even when the entries of R are non-Gaussian.”
• Fast computation of low rank matrix approximations (2001, methodology): “We state below an extension of the F uredi{Koml os bound to non-symmetric matrices, strengthened by recent sharp concentration bounds due to Krivelevich and Vu [11].”
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication (2006, methodology): “The theorem is proved by using a generalization of a result of Füredi and Komlós [16], combined with a more recent concentration result of Krivelevich and Vu based on Talagrand’s inequality [21].”
• TAIL BOUNDS FOR ALL EIGENVALUES OF A SUM OF RANDOM MATRICES (2011, methodology): “on in particular the work of Achlioptas and McSherry on randomized sparsication of matrices [AM01, AM07], that of Meckes on the norms of random matrices [Mec04], and that of Alon, Krivelevich and Vu [AKV02] on the concentration of the largest eigenvalues of random symmetric matrices, all of which ar”
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, result): “Finally, we note that our result is not quite comparable concentration bounds of Alon, Krivelevich and Vu [6] for the largest eigenvalues of a random symmetric matrix.”
• Outliers in the spectrum of iid matrices with bounded rank perturbations (2010, background): “r [9, Theorem 5.17]. We remark that the tail bound can also be deduced from the main result using the Talagrand concentration inequality (after rst truncating to the case when xis bounded); see [28], [1], [32]. The precise expression m+ 1 is not important for our arguments here; any quantity that wa”
• A new approach to the planted clique problem (2008, unknown): “It is known [3] that with probability at least 1 − 4e−10|S| log n, we have that |λ1(M̂)| ≤ 100 √ |S| log n.”
• Rigidity of eigenvalues of generalized Wigner matrices (2010, background): “The resolvent G([1]) = (H [1] − z)−1 is now independent of all expansion variables hν with ν ∈ Q = Q1 ∪ Q2.”
• Spectral partitioning of random graphs (2001, result): “The following is a classic expectation result of Furedi and Komlos [12], combined with a recent concentration result of Krivelevich and Vu [ 17 ].”
• Spectral Graph Theory (2012, methodology): “Using results from random matrix theory of Füredi and Komlós [77], Vu [78], and Alon, Krievlevich and Vu [79], McSherry proves that G is a slight perturbation of H , and that the eigenvectors of G can be used to recover the set S, with high probability.”
• Graphs with integral spectrum (2009, background): “u t The following result from [2] is also crucial for what follows.”
• Sparse regular random graphs: Spectral density and eigenvectors (2009, background): “Semerjian and Gugliandolo [52], Bordenave and Lelarge [13], Bhamidi, Evans and Sen [12]). Other properties include concentration of eigenvalues (Krivelevich and Sudakov [39], Alon, Krivelevich and Vu [1]), the spectral gap (Fu˝redi and Komlo´s [32], Friedman [29] and Friedman and Alon [31], Broder a”
• Random matrices: Sharp concentration of eigenvalues (2012, background): “10 One could also use the earlier estimates in [28] or [2]; see also [3] for more discussion.”