TAIL BOUNDS FOR ALL EIGENVALUES OF A SUM OF RANDOM MATRICES

By Alex Gittens, Joel A. Tropp. 2011

54 citations recorded by the source corpus.

This work introduces the minimax Laplace transform method, a modification of the cumulant-based matrix Laplace transform method developed in [Tro11c] 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 analogs 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. Here, the behavior of the singular values can be described in terms of coherence-like quantities. The second example addresses the question of relative accuracy in the estimation of eigenvalues of the covariance matrix of a random process. Standard results on the convergence of sample covariance matrices provide bounds on the number of samples needed to obtain relative accuracy in the spectral norm, but these results only guarantee relative accuracy in the estimate of the maximum eigenvalue. The minimax Laplace transform argument establishes that if the lowest eigenvalues decay sufficiently fast, Ω(e^(-2)κ^2_l l log p) samples, where κ_l = λ_1(C)/λ_l(C), are sufficient to ensure that the dominant l eigenvalues of the covariance matrix of a N(0,C) random vector are estimated to within a factor of 1 ± e with high probability.

Subfields: Computational Mechanics, Statistics and Probability, Signal Processing

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

How researchers see this paper

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

In Computational Mechanics

In Statistics and Probability

In Signal Processing

Citations in the corpus

Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priors (2018, methodology): “…that E [ AA T ] = I (since the rows of A are sampled from the distribution N (0 , 1 d I ) ), and thus, by the covariance estimation theorem of Gittens and Tropp [GT11] (see Corollary 7.2) (and union bounding over the two relevant events), we have that and thus with probability at least 1 − +1 p .”
Linear Convergence with Condition Number Independent Access of Full Gradients (2013, methodology): “In particular, the Hessian matrix estimated from a subset of functions, combined with the concentration inequalities for matrix [7], can be used to bound the eigenvalues of the true Hessian matrix and consequentially κ.”
Time-uniform Chernoff bounds via nonnegative supermartingales (2018, background): “See also Vershynin (2012), Gittens and Tropp (2011), Tropp (2015), and Koltchinskii and Lounici (2017) for more recent treatments; this particular example is drawn from Wainwright (2017). Let d ≥ 2 and consider R-valued, mean-zero observations Xi = √ dξieUi , where ξi iid ∼ Rademacher, (ek)k=1 are t”
Time-uniform, nonparametric, nonasymptotic confidence sequences (2018, background): “We now consider the nonasymptotic sequential estimation of a covariance matrix based on bounded vector observations [22, 39, 62, 70, 71].”
On Singular Values of Random Matrices (2015, background): “[11] Consider a finite sequence Xi of independent of centered self-adjoint random n × n matrices.”
Uniform, nonparametric, non-asymptotic confidence sequences (2018, methodology): “Here we consider a more practical problem: non-asymptotic sequential estimation of a covariance matrix based on bounded vector observations (Rudelson, 1999; Vershynin, 2012; Gittens and Tropp, 2011; Tropp, 2015; Koltchinskii and Lounici, 2017).”