Matrix Concentration Inequalities via the Method of Exchangeable Pairs

Authors

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

Year

2012

Journal Paper

Source

Annals of Probability

Identifiers

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.

Summary¶

Extends Chatterjee's exchangeable-pairs version of Stein's method from scalar to self-adjoint matrix-valued random variables, producing exponential and moment inequalities for spectral norms. It is useful because it recovers matrix Hoeffding, Bernstein, Khintchine, and Rosenthal bounds in one framework and also handles dependent matrix functions that are awkward for independence-only proofs.