Matrix measure concentration inequalities and bounds



Concentration inequalities for matrix-valued random variables.

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

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.

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}. \]

Matrix Bernstein

TBC.

Matrix Efron-Stein

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

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

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. \]

References

Ahlswede, R., and A. Winter. 2002. “Strong Converse for Identification via Quantum Channels.” IEEE Transactions on Information Theory 48 (3): 569–79. https://doi.org/10.1109/18.985947.
Bach, Francis R. 2013. “Sharp Analysis of Low-Rank Kernel Matrix Approximations.” In COLT, 30:185–209. http://www.jmlr.org/proceedings/papers/v30/Bach13.pdf.
Bishop, Adrian N., Pierre Del Moral, and Angèle Niclas. 2018. “An Introduction to Wishart Matrix Moments.” Foundations and Trends® in Machine Learning 11 (2): 97–218. https://doi.org/10.1561/2200000072.
Boucheron, Stéphane, Gábor Lugosi, and Pascal Massart. 2013. Concentration Inequalities: A Nonasymptotic Theory of Independence. 1st ed. Oxford: Oxford University Press.
———. n.d. Concentration Inequalities: A Nonasymptotic Theory of Independence. Concentration Inequalities. Oxford University Press. Accessed March 3, 2021. https://oxford.universitypressscholarship.com/view/10.1093/acprof:oso/9780199535255.001.0001/acprof-9780199535255.
Bousquet, Olivier, Ulrike von Luxburg, and Gunnar Rtsch. 2004. Advanced Lectures on Machine Learning: ML Summer Schools 2003, Canberra, Australia, February 2-14, 2003, T Bingen, Germany, August 4-16, 2003, Revised Lectures. Springer.
Brault, Romain, Florence d’Alché-Buc, and Markus Heinonen. 2016. “Random Fourier Features for Operator-Valued Kernels.” In Proceedings of The 8th Asian Conference on Machine Learning, 110–25. http://arxiv.org/abs/1605.02536.
Candès, Emmanuel J., and Benjamin Recht. 2009. “Exact Matrix Completion via Convex Optimization.” Foundations of Computational Mathematics 9 (6): 717–72. https://doi.org/10.1007/s10208-009-9045-5.
Geer, Sara van de. 2014. “Statistical Theory for High-Dimensional Models.” September 30, 2014. http://arxiv.org/abs/1409.8557.
Gross, D. 2011. “Recovering Low-Rank Matrices From Few Coefficients in Any Basis.” IEEE Transactions on Information Theory 57 (3): 1548–66. https://doi.org/10.1109/TIT.2011.2104999.
Gross, David, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, and Jens Eisert. 2010. “Quantum State Tomography via Compressed Sensing.” Physical Review Letters 105 (15). https://doi.org/10.1103/PhysRevLett.105.150401.
Handel, Ramon van. 2017. “Structured Random Matrices.” In Convexity and Concentration, edited by Eric Carlen, Mokshay Madiman, and Elisabeth M. Werner, 107–56. The IMA Volumes in Mathematics and Its Applications. New York, NY: Springer. https://doi.org/10.1007/978-1-4939-7005-6_4.
Mahoney, Michael W. 2016. “Lecture Notes on Spectral Graph Methods.” 2016. http://arxiv.org/abs/1608.04845.
Marton, Katalin. 2015. “Logarithmic Sobolev Inequalities in Discrete Product Spaces: A Proof by a Transportation Cost Distance.” July 10, 2015. http://arxiv.org/abs/1507.02803.
Massart, Pascal. 2007. Concentration Inequalities and Model Selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII - 2003. Lecture Notes in Mathematics 1896. Berlin ; New York: Springer-Verlag. http://www.cmap.polytechnique.fr/~merlet/articles/probas_massart_stf03.pdf.
Mohri, Mehryar, Afshin Rostamizadeh, and Ameet Talwalkar. 2018. Foundations of Machine Learning. Second edition. Adaptive Computation and Machine Learning. Cambridge, Massachusetts: The MIT Press.
Oliveira, Roberto Imbuzeiro. 2010. “The Spectrum of Random $k$-Lifts of Large Graphs (with Possibly Large $k$).” Journal of Combinatorics 1 (3): 285–306. https://doi.org/10.4310/JOC.2010.v1.n3.a2.
Paulin, Daniel, Lester Mackey, and Joel A. Tropp. 2016. “Efron–Stein Inequalities for Random Matrices.” The Annals of Probability 44 (5): 3431–73. https://doi.org/10.1214/15-AOP1054.
Stam, A. J. 1982. “Limit Theorems for Uniform Distributions on Spheres in High-Dimensional Euclidean Spaces.” Journal of Applied Probability 19 (1): 221–28. https://doi.org/10.2307/3213932.
Tropp, Joel. 2019. Matrix Concentration & Computational Linear Algebra / ENS Short Course.
Tropp, Joel A. 2015. An Introduction to Matrix Concentration Inequalities. http://arxiv.org/abs/1501.01571.
Vershynin, Roman. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. 1st ed. Cambridge University Press. https://doi.org/10.1017/9781108231596.
Woodruff, David P. 2014. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends in Theoretical Computer Science 1.0. Now Publishers. https://doi.org/10.1561/0400000060.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.