Matrix concentration inequalities via the method of exchangeable pairs
arXiv:1201.6002 · doi:10.1214/13-AOP892
Abstract
This paper derives exponential concentration inequalities and polynomial moment inequalities for the spectral norm of a random matrix. The analysis requires a matrix extension of the scalar concentration theory developed by Sourav Chatterjee using Stein's method of exchangeable pairs. When applied to a sum of independent random matrices, this approach yields matrix generalizations of the classical inequalities due to Hoeffding, Bernstein, Khintchine and Rosenthal. The same technique delivers bounds for sums of dependent random matrices and more general matrix-valued functions of dependent random variables.
arXiv commentPublished in at http://dx.doi.org/10.1214/13-AOP892 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (9)
- A Simpler Approach to Matrix Completion
- User-friendly tail bounds for sums of random matrices
- Recovering low-rank matrices from few coefficients in any basis
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Non-commutative martingale inequalities
- Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
- Noncommutative Bennett and Rosenthal inequalities
- Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
- The spectral norm error of the naive Nystrom extension
Cited by in corpus (11)
- Kernel Manifold Alignment
- Time-uniform Chernoff bounds via nonnegative supermartingales
- Preconditioned Data Sparsification for Big Data with Applications to PCA and K-means
- Structured Random Matrices
- Subadditivity of Matrix phi-Entropy and Concentration of Random Matrices
- Bernstein type inequality for a class of dependent random matrices
- Concentration Inequalities for Sums of Markov Dependent Random Matrices
- Distribution of singular values of random band matrices; Marchenko-Pastur law and more
- Matrix Infinitely Divisible Series: Tail Inequalities and Their Applications
- Riemannian Stochastic Variance-Reduced Cubic Regularized Newton Method for Submanifold Optimization
- Sharp concentration for sums of matrices with Markovian dependence through universality