User-friendly tail bounds for sums of random matrices

Abstract

This paper presents new probability inequalities for sums of independent, random, self-adjoint matrices. These results place simple and easily verifiable hypotheses on the summands, and they deliver strong conclusions about the large-deviation behavior of the maximum eigenvalue of the sum. Tail bounds for the norm of a sum of random rectangular matrices follow as an immediate corollary. The proof techniques also yield some information about matrix-valued martingales. In other words, this paper provides noncommutative generalizations of the classical bounds associated with the names Azuma, Bennett, Bernstein, Chernoff, Hoeffding, and McDiarmid. The matrix inequalities promise the same diversity of application, ease of use, and strength of conclusion that have made the scalar inequalities so valuable.

Current paper is the version of record. The material on Freedman's inequality has been moved to a separate note; other martingale bounds are described in Caltech ACM Report 2011-01

References in corpus (4)

• Sparsity and Incoherence in Compressive Sampling
• Recovering low-rank matrices from few coefficients in any basis
• A Matrix Convexity Approach to Some Celebrated Quantum Inequalities
• From joint convexity of quantum relative entropy to a concavity theorem of Lieb

Cited by in corpus (140)

• Matrix Completion Methods for Causal Panel Data Models
• An overview of low-rank matrix recovery from incomplete observations
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Consistency of spectral clustering in stochastic block models
• Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
• Fast community detection by SCORE
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Provably efficient machine learning for quantum many-body problems
• Robust Spectral Compressed Sensing via Structured Matrix Completion
• Self-Calibration and Biconvex Compressive Sensing
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Incoherence-Optimal Matrix Completion
• Optimal Uniform Convergence Rates and Asymptotic Normality for Series Estimators Under Weak Dependence and Weak Conditions
• Guaranteed Blind Sparse Spikes Deconvolution via Lifting and Convex Optimization
• Coherence Motivated Sampling and Convergence Analysis of Least-Squares Polynomial Chaos Regression
• A general framework for randomized benchmarking
• Noisy low-rank matrix completion with general sampling distribution
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Sparse Polynomial Chaos Expansions via Compressed Sensing and D-optimal Design
• A Partial Derandomization of PhaseLift using Spherical Designs
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Time-uniform Chernoff bounds via nonnegative supermartingales
• Multivariate Trace Inequalities
• Matrix Completion via Max-Norm Constrained Optimization
• Matrix concentration inequalities via the method of exchangeable pairs
• On Polynomial Chaos Expansion via Gradient-enhanced ${\ell }_1$-minimization
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Toward a Spectral Theory of Cellular Sheaves
• Concentration for random product formulas
• Posterior contraction in sparse Bayesian factor models for massive covariance matrices
• Low Rank Phase Retrieval
• Modal Analysis with Compressive Measurements
• Integral norm discretization and related problems
• On the sample covariance matrix estimator of reduced effective rank population matrices, with applications to fPCA
• Noncommutative Bennett and Rosenthal inequalities
• Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
• Infinite dimensional compressed sensing from anisotropic measurements and applications to inverse problems in PDE
• Statistical analysis of latent generalized correlation matrix estimation in transelliptical distribution
• Basis Adaptive Sample Efficient Polynomial Chaos (BASE-PC)
• Projected Least-Squares Quantum Process Tomography
• Convex recovery of continuous domain piecewise constant images from non-uniform Fourier samples
• Bayesian calibration and sensitivity analysis for a karst aquifer model using active subspaces
• Optimal pointwise sampling for $L^2$ approximation
• Learning Model-Based Sparsity via Projected Gradient Descent
• Classical shadow tomography for continuous variables quantum systems
• Utilization of the Wavefront Sensor and Short-Exposure Images for Simultaneous Estimation of Quasi-static Aberration and Exoplanet Intensity
• Data-driven distributionally robust MPC for constrained stochastic systems
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• Provable Dynamic Robust PCA or Robust Subspace Tracking
• Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
• Randomized linear algebra for model reduction. Part I: Galerkin methods and error estimation
• A comparative study of estimation methods in quantum tomography
• Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas
• Efficient Approximation of Quantum Channel Capacities
• Localization from Incomplete Euclidean Distance Matrix: Performance Analysis for the SVD-MDS Approach
• Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss
• Rank penalized estimation of a quantum system
• The Golden-Thompson inequality --- historical aspects and random matrix applications
• On Fully Dynamic Graph Sparsifiers
• Subadditivity of Matrix phi-Entropy and Concentration of Random Matrices
• Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
• Approximate quantum Markov chains
• Boosted optimal weighted least-squares
• Sparse Blind Deconvolution and Demixing Through ${\ell }_{1,2}$-Minimization
• Simultaneous Sparse Recovery and Blind Demodulation
• Community detection by spectral methods in multi-layer networks
• Approximating smooth, multivariate functions on irregular domains
• Laplacian Eigenmaps from Sparse, Noisy Similarity Measurements
• Interpretable Approximation of High-Dimensional Data
• Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise
• Projected Gradient Descent for Spectral Compressed Sensing via Symmetric Hankel Factorization
• Identification Via Quantum Channels
• Community detection for weighted bipartite networks
• Spectral thresholding quantum tomography for low rank states
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• Noncommutative martingale concentration inequalities
• Bernstein type inequality for a class of dependent random matrices
• Simplicial faces of the set of correlation matrices
• Pattern Formation in Random Networks Using Graphons
• Blind Super-resolution of Point Sources via Projected Gradient Descent
• Compressive Deconvolution in Random Mask Imaging
• Variational representations related to Tsallis relative entropy
• Demixing Sines and Spikes Using Multiple Measurement Vectors
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• A local approach to parameter space reduction for regression and classification tasks
• A useful criterion on studying consistent estimation in community detection
• Matrix factorization for multivariate time series analysis
• User-friendly confidence regions for quantum state tomography
• Approximating Hamiltonian dynamics with the Nyström method
• Community detection and percolation of information in a geometric setting
• High-dimensional estimation of quadratic variation based on penalized realized variance
• Nearly Optimal Stochastic Approximation for Online Principal Subspace Estimation
• Bayesian inference for spectral projectors of the covariance matrix
• Nonparametric Drift Estimation from Diffusions with Correlated Brownian Motions
• Quartic quantum speedups for planted inference
• Multiple Support Recovery Using Very Few Measurements Per Sample
• Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• Concentration Inequalities for Sums of Markov Dependent Random Matrices
• Open and closed random walks with fixed edgelengths in ${\mathbb{R}}^d$
• Exponential speedups for quantum walks in random hierarchical graphs
• Distribution of singular values of random band matrices; Marchenko-Pastur law and more
• Asymmetric Graph Error Control with Low Complexity in Causal Bandits
• Memory capacity of two layer neural networks with smooth activations
• Estimation of low rank density matrices by Pauli measurements
• Low rank estimation of smooth kernels on graphs
• On a bound of Hoeffding in the complex case
• Random periodic sampling patterns for shift-invariant spaces
• Phase retrieval using random cubatures and fusion frames of positive semidefinite matrices
• Improving quantum state detection with adaptive sequential observations
• Preconditioning filter bank decompositions using structured normalized tight frames
• Minimax Hypothesis Testing for the Bradley-Terry-Luce Model
• On U-Statistics and Compressed Sensing II: Non-Asymptotic Worst-Case Analysis
• Anomaly Detection-Based UE-Centric Inter-Cell Interference Suppression
• Signal Analysis based on Complex Wavelet Signs
• Approximation of Functions: Optimal Sampling and Complexity
• Properties of Discrete Sliced Wasserstein Losses
• Error Bounds of the Invariant Statistics in Machine Learning of Ergodic Itô Diffusions
• Matrix Infinitely Divisible Series: Tail Inequalities and Their Applications
• Unique reconstruction for discretized inverse problems: a random sketching approach via subsampling
• Random-reshuffled SARAH does not need a full gradient computations
• Linear Contextual Bandits with Hybrid Payoff: Revisited
• Embracing Off-the-Grid Samples
• Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
• Expected communication cost of distributed quantum tasks
• Concentration of quantum channels with random Kraus operators via matrix Bernstein inequality
• Kernel VICReg for Self-Supervised Learning in Reproducing Kernel Hilbert Space
• An elementary analysis of ridge regression with random design
• Interacting Particle Systems on Networks: joint inference of the network and the interaction kernel
• Nonparametric Estimation of Low Rank Matrix Valued Function
• Concentration and moment inequalities for sums of independent heavy-tailed random matrices
• Clustered Covariate Regression
• Norms of structured random matrices
• A Martingale-Free Introduction to Conditional Gaussian Nonlinear Systems
• Capturing the critical coupling of large random Kuramoto networks with graphons
• A Unified Framework for Community Detection and Model Selection in Blockmodels
• Persistence of steady-states for dynamical systems on large networks
• Optimizing Sparse SYK
• Efficient classical computation of the neural tangent kernel of quantum neural networks