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.
The statistical properties of the characteristic values of a matrix the elements of which show a normal (Gaussian) distribution are well known (cf. [6] Chapter XI) and have been derived, rather recently, in a particularly elegant fashion.1 The present problem arose from the consideration of the properties of the wave functions of quantum mechanical systems which are assumed to be so complicated that statistical considerations can be applied to them. Since the physical problem has been given rather recently in some detail in another journal [3], it will not be reviewed here. Actually, the model which underlies the present calculations shows only a limited similarity to the model which is believed to be correct. Nevertheless, the calculation which follows may have some independent interest; it certainly provided the encouragement for a detailed investigation of the model which may reproduce some features of the actual behavior of atomic nuclei.