# Matrix measure concentration inequalities and bounds

November 25, 2014 — March 8, 2021

Concentration inequalities for matrix-valued random variables, which are, loosely speaking, promises that some matrix is close to some known value measured in some metric with some probability.

Recommended overviews are J. A. Tropp (2015);van Handel (2017);Vershynin (2018).

## 1 Matrix Chernoff

J. A. Tropp (2015) summarises:

In recent years, random matrices have come to play a major role in computational mathematics, but most of the classical areas of random matrix theory remain the province of experts. Over the last decade, with the advent of matrix concentration inequalities, research has advanced to the point where we can conquer many (formerly) challenging problems with a page or two of arithmetic.

Are these related?

Nikhil Srivastava’s Discrepancy, Graphs, and the Kadison-Singer Problem has an interesting example of bounds via discrepancy theory (and only indirectly probability). D. Gross (2011) is also readable, and gives results for matrices over the complex field.

## 2 Matrix Chebychev

As discussed in, e.g. Paulin, Mackey, and Tropp (2016).

Let \(\mathbf{X} \in \mathbb{H}^{d}\) be a random matrix. For all \(t>0\) \[ \mathbb{P}\{\|\mathbf{X}\| \geq t\} \leq \inf _{p \geq 1} t^{-p} \cdot \mathbb{E}\|\mathbf{X}\|_{S_{p}}^{p} \] Furthermore, \[ \mathbb{E}\|\mathbf{X}\| \leq \inf _{p \geq 1}\left(\mathbb{E}\|\mathbf{X}\|_{S_{p}}^{p}\right)^{1 / p}. \]

## 3 Matrix Bernstein

TBC. Bounds the spectral norm.

## 4 Matrix Efron-Stein

The “classical” Efron-Stein inequalities are simple. The Matrix ones, not so much

e.g. Paulin, Mackey, and Tropp (2016).

## 5 Gaussian

Handy results from Vershynin (2018):

Takes \(X \sim N\left(0, I_{n}\right).\)

Show that, for any fixed vectors \(u, v \in \mathbb{R}^{n},\) we have \[ \mathbb{E}\langle X, u\rangle\langle X, v\rangle=\langle u, v\rangle \]

Given a vector \(u \in \mathbb{R}^{n}\), consider the random variable \(X_{u}:=\langle X, u\rangle .\)

Further, we know that \(X_{u} \sim N\left(0,\|u\|_{2}^{2}\right) .\) It follows that \[ \mathbb{E}\left[(X_{u}-X_{v})^2\right]^{1/2}=\|u-v\|_{2} \] for any fixed vectors \(u, v \in \mathbb{R}^{n} .\)

Grothendieck’s identity: For any fixed vectors \(u, v \in S^{n-1},\) we have \[ \mathbb{E} \operatorname{sign}X_{u} \operatorname{sign}X_{v}=\frac{2}{\pi} \arcsin \langle u, v\rangle. \]

- Nick Higham, Eigenvalue Inequalities for Hermitian Matrices

## 6 References

*IEEE Transactions on Information Theory*.

*Operator Theory in Function Spaces and Banach Lattices: Essays Dedicated to A.C. Zaanen on the Occasion of His 80th Birthday*. Operator Theory Advances and Applications.

*COLT*.

*Rocky Mountain Journal of Mathematics*.

*Matrix Analysis*. Graduate Texts in Mathematics.

*Bulletin of the London Mathematical Society*.

*Foundations and Trends® in Machine Learning*.

*Concentration Inequalities: A Nonasymptotic Theory of Independence*.

*Advanced Lectures on Machine Learning: ML Summer Schools 2003, Canberra, Australia, February 2-14, 2003, T Bingen, Germany, August 4-16, 2003, Revised Lectures*.

*Proceedings of The 8th Asian Conference on Machine Learning*.

*Integral Equation and Operator Theory*.

*Foundations of Computational Mathematics*.

*Annals of Functional Analysis*.

*IEEE Transactions on Information Theory*.

*Physical Review Letters*.

*Linear Algebra and Its Applications*.

*Operator Theory in Function Spaces and Banach Lattices: Essays Dedicated to A.C. Zaanen on the Occasion of His 80th Birthday*.

*Journal of Inequalities and Applications*.

*Matrix differential calculus with applications in statistics and econometrics*. Wiley series in probability and statistics.

*arXiv Preprint arXiv:1608.04845*.

*arXiv:1507.02803 [Math]*.

*Concentration Inequalities and Model Selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII - 2003*. Lecture Notes in Mathematics 1896.

*Journal of Mathematical Analysis and Applications*.

*Foundations of Machine Learning*. Adaptive Computation and Machine Learning.

*Journal of Combinatorics*.

*The Annals of Probability*.

*Journal of Mathematical Inequalities*.

*Journal of Applied Probability*.

*An Introduction to Matrix Concentration Inequalities*.

*Matrix Concentration & Computational Linear Algebra / ENS Short Course*.

*Advances in Operator Theory*.

*arXiv:1409.8557 [Math, Stat]*.

*Convexity and Concentration*. The IMA Volumes in Mathematics and Its Applications.

*arXiv:1011.3027 [Cs, Math]*.

*Sampling Theory, a Renaissance: Compressive Sensing and Other Developments*. Applied and Numerical Harmonic Analysis.

*High-Dimensional Statistics: A Non-Asymptotic Viewpoint*. Cambridge Series in Statistical and Probabilistic Mathematics 48.

*Sketching as a Tool for Numerical Linear Algebra*. Foundations and Trends in Theoretical Computer Science 1.0.