2011

Tail bounds for all eigenvalues of a sum of random matrices

Gittens, Alex, Tropp, Joel A.

Understand

This work introduces the minimax Laplace transform method, a modification of the cumulant-based matrix Laplace transform method developed in "User-friendly tail bounds for sums of random matrices" (arXiv:1004.4389v6) that yields both upper and lower bounds on each eigenvalue of a sum of random self-adjoint matrices.

This machinery is used to derive eigenvalue analogues of the classical Chernoff, Bennett, and Bernstein bounds.
Two examples demonstrate the efficacy of the minimax Laplace transform.
The first concerns the effects of column sparsification on the spectrum of a matrix with orthonormal rows.

Built on

E. P. Wigner, Characteristic vectors of bordered matrices with infinite dimensions , Annals Math. 62
1955
Earlier work this paper cites.
U. Grenander, Probabilities on Algebraic Structures , John Wiley & Sons, Inc., 1963
1963
Earlier work this paper cites.
V. A. Marc̆enko and L. A. Pastur, Distributions of eigenvalues for some sets of random matrices , Math. USSR Sb. 1
1967
Earlier work this paper cites.
L. Arnold, On Wigner’s semicircle law for the eigenvalues of random matrices , Z. Wahrsch. Verw. Gebiete 19
1971
Earlier work this paper cites.
E. H. Lieb, Convex trace functions and the Wigner–Yanase–Dyson conjecture , Adv. Math. 11
1973
Earlier work this paper cites.
S. Gemon, A limit theorem for the norm of random matrices , Ann. Probab. 8
1980
Earlier work this paper cites.
F. Lust-Piquard, Inégalités de Khintchine dans C p C_{p} ( 1 < p < ∞ ) (1<p<\infty) , C. R. Math. Acad. Sci. Paris 303
1986
Earlier work this paper cites.
Z. D. Bai, J. W. Silverstein, and Y. Q. Yin, A note on the largest eigenvalue of a large dimensional sample covariance matrix , J. Multivariate Anal. 26
1988
Earlier work this paper cites.
Z. D. Bai and Y. Q. Yin, A convergence to the semicircle law , Ann. Probab. 16
1988
Earlier work this paper cites.
by same author, Necessary and sufficient conditions for the almost sure convergence of the largest eigenvalue of Wigner matrices , Ann. Probab. 16
1988
Earlier work this paper cites.
Y. Q. Yin, Z. D. Bai, and P. R. Krishnaiah, On the limit of the largest eigenvalue of the large dimensional sample covariance matrix , Probab. Theory Relat. Fields 78
Original
1988
Earlier work this paper cites.
S. J. Szarek, Spaces with large distance to ℓ ∞ n \ell^{n}_{\infty} and random matrices , Amer. J. Math. 112
1990
Earlier work this paper cites.
F. Lust-Piquard and G. Pisier, Noncommutative Khintchine and Paley Inequalities , Ark. Mat. 29
1991
Earlier work this paper cites.
Z. D. Bai, Convergence rate of expected spectral distributions of large random matrices. Part I. Wigner matrices , Ann. Probab. 21
1993
Earlier work this paper cites.
by same author, Convergence rate of expected spectral distributions of large random matrices. Part II. Sample covariance matrices , Ann. Probab. 21
1993
Earlier work this paper cites.
J. Lindenstrauss and V. D. Milman, Handbook of convex geometry , vol. B, ch. The Local Theory of Normed Spaces and Its Applications to Convexity, pp. 1149–1220, Elsevier Science Publishers B.V., 1993
1993
Earlier work this paper cites.
M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces , Inst. Hautes Études Sci. Publ. Math. 81
1995
Earlier work this paper cites.
Z. Rudnick and P. Sarnack, Zeros of principal L-functions and random matrix theory , Duke Math. J. 81
1996
Earlier work this paper cites.
Z. D. Bai, B. Q. Miao, and J. Tsay, A note on the convergence rate of the spectral distributions of large dimensional random matrices , Statist. Probab. Lett. 34
1997
Earlier work this paper cites.
V. De la Peña and E. Giné, Decoupling: From Dependence to Independence , Probability and its Applications, Springer, 1998
1998
Earlier work this paper cites.
T. Guhr, A. Müller-Groeling, and H. A. Weidenmüller, Random matrix theories in quantum physics: common concepts , Phys. Rep. 299
1998
Earlier work this paper cites.
M. V. Berry and J. P. Keating, The Riemann Zeros and Eigenvalue Asymptotics , SIAM Rev. 41
1999
Earlier work this paper cites.
by same author, Remarks on the convergence rate of the spectral distributions of Wigner matrices. , J. Theoret. Probab. 12
1999
Earlier work this paper cites.
M. Rudelson, Random Vectors in the Isotropic Position , J. Funct. Anal. 164
1999
Earlier work this paper cites.
D. Achlioptas and F. McSherry, Fast Computation of Low Rank Matrix Approximations , Proc. 33rd ACM Symposium on Theory of Computing (STOC 2001), 2001, pp. 611–618
2001
Earlier work this paper cites.
I. M. Johnstone, On the distribution of the largest eigenvalue in principal components analysis , Ann. Statist. 29
2001
Earlier work this paper cites.
S. J. Szarek and K. R. Davidson, Handbook on the Geometry of Banach spaces , ch. Local operator theory, random matrices, and Banach spaces, pp. 317–366, North Holland, 2001
2001
Earlier work this paper cites.

Similar

N. Alon, M. Krivelevich, and V. H. Vu, On the concentration of eigenvalues of random symmetric matrices , Israel J. Math. 131
2002
Cited alongside, same era.
R. Ahlswede and A. Winter, Strong converse for identification via quantum channels , IEEE Trans. Inform. Theory 48
2002
Cited alongside, same era.
by same author, Convergence rates of the spectral distributions of large Wigner matrices , Int. Math. J. 1
2002
Cited alongside, same era.
D. Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins , J. Comput. System Sci. 66
2003
Cited alongside, same era.
Z. D. Bai, B. Q. Miao, and J. F. Yao, Convergence rates of spectral distributions of large sample covariance matrices. , SIAM J. Matrix Anal. Appl. 25
2003
Cited alongside, same era.
M. W. Meckes, Concentration of norms and eigenvalues of random matrices , J. Funct. Anal. 211
2004
Cited alongside, same era.
M. L. Mehta, Random Matrices , Third ed., Academic Press, 2004
2004
Cited alongside, same era.
A. M. Tulino and S. Verdu, Random Matrix Theory and Wireless Communication , Now Publishers Inc., 2004
2004
Cited alongside, same era.
S. S. Vempala, The Random Projection Method , AMS, 2004
2004
Cited alongside, same era.
Z. Chen and J. J. Dongarra, Condition numbers of Gaussian random matrices , SIAM J. Matrix Anal. Appl. 27
2005
Cited alongside, same era.
P. Drineas and M. W. Mahoney, On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning , J. Mach. Learn. Res. 6
2005
Cited alongside, same era.
J. Gustavsson, Gaussian fluctuations of eigenvalues in the GUE , Ann. Inst. Henri Poincaré Probab. Stat. 41
2005
Cited alongside, same era.

Then

D. A. Spielman and N. Srivastava, Graph sparsification by effective resistances , Proc. 40th ACM Symposium on Theory of Computing (STOC 2008), 2008
2008
Later among the works it cites.
J. A. Tropp, On the conditioning of random subdictionaries , Appl. Comput. Harmon. Anal. 25
2008
Later among the works it cites.
R. I. Oliveira, Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges , Preprint, arXiv:0911.0600, 2009
Original
2009
Later among the works it cites.
B. Recht, A simpler approach to matrix completion , To appear in J. Mach. Learn. Res., 2009
2009
Later among the works it cites.
A. M. So, Moment inequalities for sums of random matrices and their applications in optimization , Math. Program. (2009), 1–27
2009
Later among the works it cites.
by same author, Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving , Preprint, arXiv:1005.3097, 2010
Original
2010
Later among the works it cites.
L. Erdös, H. Yau, and J. Yin, Rigidity of Eigenvalues of Generalized Wigner Matrices , Preprint, arXiv:1007.4652, 2010
Original
2010
Later among the works it cites.
B. Farrell, Limiting Empirical Singular Value Distribution of Restrictions of Discrete Fourier Transform Matrices , J. Fourier Anal. Appl. (2010), 1–21
2010
Later among the works it cites.
S. Gurevich and R. Hadani, The statistical restricted isometry property and the Wigner semicircle distribution of incoherent dictionaries , Submitted to Appl. Comput. Harmon. Anal., 2010
2010
Later among the works it cites.
by same author, Sums of random Hermitian matrices and an inequality due to Rudelson , Elect. Comm. in Probab. 15
2010
Later among the works it cites.
T. Tao and V. Vu, Random Matrices: Localization of the eigenvalues and the necessity of four moments , Preprint, arXiv:1005.2901, 2010
Original
2010
Later among the works it cites.
R. Adamczak, A. E. Litvak, A. Pajor, and N. Tomczak-Jaegermann, Sharp bounds on the rate of convergence of the empirical covariance matrix , C. R. Math. Acad. Sci. Paris 349
2011
Closest in time.
Z. D. Bai, J. Hu, G. Pan, and W. Zhou, A note on rate of convergence in probability to semicircular law , Preprint, arXiv:1105.3056, 2011
Original
2011
Closest in time.
P. Drineas, M. W. Mahoney, S. Muthukrishnan, and T. Sarlós, Faster least squares approximation , Numer. Math. 117
2011
Closest in time.
D. Gross, Recovering low-rank matrices from few coefficients in any basis , IEEE Trans. Inform. Theory 57
2011
Closest in time.
D. Hsu, S. M. Kakade, and T. Zhang, Dimension-free tail inequalities for sums of random matrices , Preprint, arXiv:1104.1672, 2011
Original
2011
Closest in time.
N. Halko, P. G. Martinsson, and J. A. Tropp, Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions , SIAM Rev. 53
2011
Closest in time.
M. W. Mahoney, Randomized algorithms for matrices and data , Preprint, arXiv:1104.5557, 2011
Original
2011
Closest in time.
N. Srivastava and R. Vershynin, Covariance Estimation for Distributions with 2 + ε 2+\varepsilon Moments , Preprint, arXiv:1106.2775, 2011
Original
2011
Closest in time.
by same author, Freedman’s inequality for matrix martingales , Electron. Comm. Probab. 16
2011
Closest in time.
by same author, User-Friendly Tail Bounds for Matrix Martingales , Tech. report, California Institute of Technology, 2011, http://www.acm.caltech.edu/~jtropp/reports/Tro10-User-Friendly-Martingale-TR.pdf , retrieved June 13, 2011
2011
Closest in time.
by same author, User-Friendly Tail Bounds for Sums of Random Matrices , Accepted to Found. Comput. Math., June 2011. Preprint, arXiv:1004.4389, 2011
Original
2011
Closest in time.
by same author, Random Matrices: Universality of local eigenvalue statistics , Acta Math. 206
2011
Closest in time.
R. Vershynin, Introduction to the non-asymptotic analysis of random matrices , http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf , 2010, retrieved June 13, 2011
2011
Closest in time.
by same author, How close is the sample covariance matrix to the actual covariance matrix? , J. Theoret. Probab. (2011), 1–32
2011
Closest in time.
by same author, Random Matrices: Universality of ESDs and the circular law , Ann. Probab. 38
2065
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…