Matrix concentration inequalities via the method of exchangeable pairs

DOI10.1214/13-AOP892zbMath1294.60008arXiv1201.6002OpenAlexW3100110387WikidataQ56506296 ScholiaQ56506296MaRDI QIDQ2450243

Joel A. Tropp, Brendan Farrell, Richard Y. Chen, Michael I. Jordan, Lester Mackey

Publication date: 19 May 2014

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.6002

zbMATH Keywords

Stein's methodrandom matrixmoment inequalitiesconcentration inequalitiesnoncommutativeexchangeable pairs

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Random matrices (probabilistic aspects) (60B20) Large deviations (60F10) Exchangeability for stochastic processes (60G09)

Related Items (37)

A general parametric Stein characterization ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Sigma delta quantization with harmonic frames and partial Fourier ensembles ⋮ Restricted isometry property of principal component pursuit with reduced linear measurements ⋮ Impact of regularization on spectral clustering ⋮ Unnamed Item ⋮ On expected error of randomized Nyström kernel regression ⋮ A Stein characterisation of the generalized hyperbolic distribution ⋮ Distribution of singular values of random band matrices; Marchenko-Pastur law and more ⋮ Spherical random sampling of localized functions on 𝕊ⁿ⁻¹ ⋮ Time-uniform Chernoff bounds via nonnegative supermartingales ⋮ Subsampling spectral clustering for stochastic block models in large-scale networks ⋮ The Expected Norm of a Sum of Independent Random Matrices: An Elementary Approach ⋮ Riemannian stochastic variance-reduced cubic regularized Newton method for submanifold optimization ⋮ Stein's method for nonlinear statistics: a brief survey and recent progress ⋮ Central moment inequalities using Stein's method ⋮ Noncommutative Bennett and Rosenthal inequalities ⋮ LSV-Based Tail Inequalities for Sums of Random Matrices ⋮ Relevant sampling in finitely generated shift-invariant spaces ⋮ Near-optimality of linear recovery from indirect observations ⋮ Second-order matrix concentration inequalities ⋮ Max-norm optimization for robust matrix recovery ⋮ Concentration inequalities for matrix martingales in continuous time ⋮ Estimation from nonlinear observations via convex programming with application to bilinear regression ⋮ Approximate kernel partial least squares ⋮ Moment inequalities for matrix-valued U-statistics of order 2 ⋮ From Poincaré inequalities to nonlinear matrix concentration ⋮ Nonlinear matrix concentration via semigroup methods ⋮ Bernstein-type inequality for a class of dependent random matrices ⋮ Product mixing in the alternating group ⋮ On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models ⋮ Matrix Poincaré inequalities and concentration ⋮ Weighted Poincaré inequalities, concentration inequalities and tail bounds related to Stein kernels in dimension one ⋮ Upper and lower bounds for matrix discrepancy ⋮ Stein's method, logarithmic Sobolev and transport inequalities ⋮ Matching Component Analysis for Transfer Learning ⋮ Wasserstein-based methods for convergence complexity analysis of MCMC with applications

Uses Software

• mftoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the stability and accuracy of least squares approximations
• Tail inequalities for sums of random matrices that depend on the intrinsic dimension
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Sums of random Hermitian matrices and an inequality by Rudelson
• Freedman's inequality for matrix martingales
• Moment inequalities for sums of random matrices and their applications in optimization
• User-friendly tail bounds for sums of random matrices
• Noncommutative Burkholder/Rosenthal inequalities. II: Applications
• Non commutative Khintchine and Paley inequalities
• Distribution function inequalities for martingales
• Random vectors in the isotropic position
• Non-commutative martingale inequalities
• Noncommutative Burkholder/Rosenthal inequalities
• Optimum bounds for the distributions of martingales in Banach spaces
• Stein's method for concentration inequalities
• On the subspaces of \(L^p\) \((p > 2)\) spanned by sequences of independent random variables
• Convex trace functions and the Wigner-Yanase-Dyson conjecture
• Sublinear Randomized Algorithms for Skeleton Decompositions
• The masked sample covariance estimator: an analysis using matrix concentration inequalities
• Matrix Probing and its Conditioning
• Sampling from large matrices
• Strong converse for identification via quantum channels
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Probability Inequalities for Sums of Bounded Random Variables
• A Simpler Approach to Matrix Completion
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Functions of Matrices
• A Combinatorial Central Limit Theorem
• Operator Khintchine inequality in non-commutative probability

This page was built for publication: Matrix concentration inequalities via the method of exchangeable pairs