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.
As is the case in the asymptotic theory, the sharpest and most comprehensive results available in the nonasymptotic theory concern the behavior of Gaussian matrices. The amenability of the Gaussian distribution makes it possible to obtain results such as Szarek's nonasymptotic analog of the Wigner semicircle theorem for Gaussian matrices @cite_65 and Chen and Dongarra's bounds on the condition number of Gaussian matrices @cite_70 . The properties of less well-behaved random matrices can sometimes be related back to those of Gaussian matrices using probabilistic tools, such as symmetrization; see, e.g., the derivation of Lata a's bound on the norms of zero-mean random matrices @cite_30 .
@cite_70 @cite_65 @cite_30
2130076109 2315557445 2031213242
Let @math be an @math real random matrix whose elements are independent and identically distributed standard normal random variables, and let @math be the 2-norm condition number of @math . We prove that, for any @math , @math , and @math , @math satisfies @math where @math and @math @math are universal positive constants independent of @math , @math , and @math . Moreover, for any @math and @math , @math A similar pair of results for complex Gaussian random matrices is also established. We show that for any random matrix (X ij ) with independent mean zero entries E∥(X ij )∥ ≤ C(max √ΣEX 2 ij + max √ΣEX 2 ij + 4√ΣEX 4 ij ), where C is some universal constant.