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.
We prove concentration results for lpn operator norms of rectangular random matrices and eigenvalues of self-adjoint random matrices. The random matrices we consider have bounded entries which are independent, up to a possible self-adjointness constraint. Our results are based on an isoperimetric inequality for product spaces due to Talagrand. We present deviation inequalities of random operators of the form 1 N ∑N i=1 Xi ⊗ Xi from the average operator E(X ⊗ X), where Xi are independent random vectors distributed as X, which is a random vector in R or in 2. We use these inequalities to estimate the singular values of random matrices with independent rows (without assuming that the entries are independent). Overview and Basic Facts.- Gaussian Processes and Related Structures.- Matching Theorems.- The Bernoulli Conjecture.- Families of distances.- Applications to Banach Space Theory. The concentration of measure phenomenon in product spaces roughly states that, if a set A in a product ΩN of probability spaces has measure at least one half, “most” of the points of Ωn are “close” to A. We proceed to a systematic exploration of this phenomenon. The meaning of the word “most” is made rigorous by isoperimetrictype inequalities that bound the measure of the exceptional sets. The meaning of the work “close” is defined in three main ways, each of them giving rise to related, but different inequalities. The inequalities are all proved through a common scheme of proof. Remarkably, this simple approach not only yields qualitatively optimal results, but, in many cases, captures near optimal numerical constants. A large number of applications are given, in particular to Percolation, Geometric Probability, Probability in Banach Spaces, to demonstrate in concrete situations the extremely wide range of application of the abstract tools. Given a matrix A, it is often desirable to find a good approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when A has strong spectral features, that is, when the singular values of interest are significantly greater than those of a random matrix with size and entries similar to A. Our technique amounts to independently sampling and or quantizing the entries of A, thus speeding up computation by reducing the number of nonzero entries and or the length of their representation. Our analysis is based on observing that the acts of sampling and quantization can be viewed as adding a random matrix N to A, whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability, N has very weak spectral features, we can prove that the effect of sampling and quantization nearly vanishes when a low-rank approximation to A p N is computed. We give high probability bounds on the quality of our approximation both in the Frobenius and the 2-norm.  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 − t 232 s2. The main ingredient in the proof is Talagrand’s Inequality for concentration of measure in product spaces.  Abstract Let X 1 , … , X N ∈ R n be independent centered random vectors with log-concave distribution and with the identity as covariance matrix. We show that with overwhelming probability one has sup x ∈ S n − 1 | 1 N ∑ i = 1 N ( | 〈 X i , x 〉 | 2 − E | 〈 X i , x 〉 | 2 ) | ⩽ C n N , where C is an absolute positive constant. This result is valid in a more general framework when the linear forms ( 〈 X i , x 〉 ) i ⩽ N , x ∈ S n − 1 and the Euclidean norms ( | X i | n ) i ⩽ N exhibit uniformly a sub-exponential decay. As a consequence, if A denotes the random matrix with columns ( X i ) , then with overwhelming probability, the extremal singular values λ min and λ max of A A ⊤ satisfy the inequalities 1 − C n N ⩽ λ min N ⩽ λ max N ⩽ 1 + C n N which is a quantitative version of Bai–Yin theorem (Z.D. Bai, Y.Q. Yin, 1993 [4] ) known for random matrices with i.i.d. entries.