Subadditivity of matrix phi-entropy and concentration of random matrices

Joel A. Tropp (California Institute of Technology)
Richard Yuhua Chen (California Institute of Technology)

Abstract


This paper considers a class of entropy functionals defined for random matrices, and it demonstrates that these functionals satisfy a subadditivity property.  Several matrix concentration inequalities are derived as an application of this result.


Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-30

Publication Date: March 2, 2014

DOI: 10.1214/EJP.v19-2964

References

  • Anderson, Greg W.; Guionnet, Alice; Zeitouni, Ofer. An introduction to random matrices. Cambridge Studies in Advanced Mathematics, 118. Cambridge University Press, Cambridge, 2010. xiv+492 pp. ISBN: 978-0-521-19452-5 MR2760897
  • Ando, T. Concavity of certain maps on positive definite matrices and applications to Hadamard products. Linear Algebra Appl. 26 (1979), 203--241. MR0535686
  • Ahlswede, Rudolf; Winter, Andreas. Strong converse for identification via quantum channels. IEEE Trans. Inform. Theory 48 (2002), no. 3, 569--579. MR1889969
  • Boucheron, Stéphane; Bousquet, Olivier; Lugosi, Gabor; Massart, Pascal. Moment inequalities for functions of independent random variables. Ann. Probab. 33 (2005), no. 2, 514--560. MR2123200
  • Boutsidis, Christos; Gittens, Alex. Improved matrix algorithms via the subsampled randomized Hadamard transform. SIAM J. Matrix Anal. Appl. 34 (2013), no. 3, 1301--1340. MR3101094
  • Bhatia, Rajendra. Matrix analysis. Graduate Texts in Mathematics, 169. Springer-Verlag, New York, 1997. xii+347 pp. ISBN: 0-387-94846-5 MR1477662
  • Bhatia, Rajendra. Positive definite matrices. Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, 2007. x+254 pp. ISBN: 978-0-691-12918-1; 0-691-12918-5 MR2284176
  • Bobkov, S. G.; Ledoux, M. On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures. J. Funct. Anal. 156 (1998), no. 2, 347--365. MR1636948
  • Boucheron, Stéphane; Lugosi, Gabor; Massart, Pascal. Concentration inequalities using the entropy method. Ann. Probab. 31 (2003), no. 3, 1583--1614. MR1989444
  • Boucheron, Stéphane; Lugosi, Gabor; Massart, Pacal. On concentration of self-bounding functions. Electron. J. Probab. 14 (2009), no. 64, 1884--1899. MR2540852
  • S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities. Oxford University Press, 2013.
  • Bousquet, Olivier. A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Math. Acad. Sci. Paris 334 (2002), no. 6, 495--500. MR1890640
  • Bregman, L. M. Relaxation method for finding a common point of convex sets and its application to optimization problems. (Russian) Dokl. Akad. Nauk SSSR 171 1966 1019--1022. MR0210291
  • Carlen, Eric. Trace inequalities and quantum entropy: an introductory course. Entropy and the quantum, 73--140, Contemp. Math., 529, Amer. Math. Soc., Providence, RI, 2010. MR2681769
  • K. Chaudhuri, F. Chung, and A. Tsiatas. Spectral clustering of graphs with general degrees in the extended planted partition model. Journal of Machine Learning Research 2012, pages 1--23, 2012.
  • Cohen, Albert; Davenport, Mark A.; Leviatan, Dany. On the stability and accuracy of least squares approximations. Found. Comput. Math. 13 (2013), no. 5, 819--834. MR3105946
  • Chafaï, Djalil. Entropies, convexity, and functional inequalities: on $\Phi$-entropies and $\Phi$-Sobolev inequalities. J. Math. Kyoto Univ. 44 (2004), no. 2, 325--363. MR2081075
  • Chafaï, Djalil. Binomial-Poisson entropic inequalities and the $M/M/\infty$ queue. ESAIM Probab. Stat. 10 (2006), 317--339 (electronic). MR2247924
  • Csiszar, I. A class of measures of informativity of observation channels. Collection of articles dedicated to the memory of Alfred Rényi, I. Period. Math. Hungar. 2 (1972), 191--213. MR0335152
  • Drineas, Petros; Zouzias, Anastasios. A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality. Inform. Process. Lett. 111 (2011), no. 8, 385--389. MR2760960
  • Hansen, Frank. Trace Functions with Applications in Quantum Physics. J. Stat. Phys. 154 (2014), no. 3, 807--818. MR3163550
  • Hebisch, W.; Olkiewicz, R.; Zegarlinski, B. On upper bound for the quantum entropy. Linear Algebra Appl. 329 (2001), no. 1-3, 89--96. MR1822224
  • F. Hansen and Z. Zhang. Characterisation of matrix entropies. Available at rlarXiv.org/abs/1402.2118, Feb. 2014.
  • Junge, Marius; Xu, Quanhua. Noncommutative Burkholder/Rosenthal inequalities. Ann. Probab. 31 (2003), no. 2, 948--995. MR1964955
  • Junge, Marius; Xu, Quanhua. Noncommutative Burkholder/Rosenthal inequalities. II. Applications. Israel J. Math. 167 (2008), 227--282. MR2448025
  • M. Junge and Q. Zheng. Noncommutative Bennett and Rosenthal inequalities. Available at rlarXiv.org/abs/1111.1027, Nov. 2011.
  • Kubo, Fumio; Ando, Tsuyoshi. Means of positive linear operators. Math. Ann. 246 (1979/80), no. 3, 205--224. MR0563399
  • Ledoux, Michel. Concentration of measure and logarithmic Sobolev inequalities. Séminaire de Probabilités, XXXIII, 120--216, Lecture Notes in Math., 1709, Springer, Berlin, 1999. MR1767995
  • Ledoux, Michel. The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. x+181 pp. ISBN: 0-8218-2864-9 MR1849347
  • Ledoux, Michel. On Talagrand's deviation inequalities for product measures. ESAIM Probab. Statist. 1 (1995/97), 63--87 (electronic). MR1399224
  • Lieb, Elliott H. Convex trace functions and the Wigner-Yanase-Dyson conjecture. Advances in Math. 11 (1973), 267--288. MR0332080
  • Lieb, Elliott H. Some convexity and subadditivity properties of entropy. Bull. Amer. Math. Soc. 81 (1975), 1--13. MR0356797
  • Lindblad, Goran. Entropy, information and quantum measurements. Comm. Math. Phys. 33 (1973), 305--322. MR0337240
  • Latała, R.; Oleszkiewicz, K. Between Sobolev and Poincaré. Geometric aspects of functional analysis, 147--168, Lecture Notes in Math., 1745, Springer, Berlin, 2000. MR1796718
  • LP86:Inegalites-Khintchine F. Lust-Piquard. Inégalités de Khintchine dans C_p;(1Lieb, Elliott H.; Ruskai, Mary Beth. Proof of the strong subadditivity of quantum-mechanical entropy. With an appendix by B. Simon. J. Mathematical Phys. 14 (1973), 1938--1941. MR0345558
  • Massart, Pascal. About the constants in Talagrand's concentration inequalities for empirical processes. Ann. Probab. 28 (2000), no. 2, 863--884. MR1782276
  • Massart, Pascal. Some applications of concentration inequalities to statistics. Probability theory. Ann. Fac. Sci. Toulouse Math. (6) 9 (2000), no. 2, 245--303. MR1813803
  • S. Minsker. On some extensions of Bernstein's inequality for self-adjoint operators. Available at rlarXiv.org/abs/1112.5448, Jan. 2012.
  • L. Mackey, M. I. Jordan, R. Y. Chen, B. Farrell, and J. A. Tropp. Matrix concentration inequalities via the method of exchangeable pairs. Available at rlarXiv.org/abs/1201.6002, 2012.
  • R. I. Oliveira. Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges. Available at rlarXiv.org/abs/0911.0600, 2009.
  • Petz, Dénes. A survey of certain trace inequalities. Functional analysis and operator theory (Warsaw, 1992), 287--298, Banach Center Publ., 30, Polish Acad. Sci., Warsaw, 1994. MR1285615
  • D. Paulin, L. Mackey, and J. A. Tropp. Deriving matrix concentration inequalities from kernel couplings. Available at rlarXiv.org/abs/1305.0612, May 2013.
  • Rényi, Alfred. On measures of entropy and information. 1961 Proc. 4th Berkeley Sympos. Math. Statist. and Prob., Vol. I pp. 547--561 Univ. California Press, Berkeley, Calif. MR0132570
  • Rio, Emmanuel. Inégalités de concentration pour les processus empiriques de classes de parties. (French) [Concentration inequalities for set-indexed empirical processes] Probab. Theory Related Fields 119 (2001), no. 2, 163--175. MR1818244
  • M. Raginsky and I. Sason. Concentration of measure inequalities in information theory, communications and coding. Foundations and Trends in Communications and Information Theory, 10(1--2):1--246, 2013. Available at rlarXiv.org/abs/1212.4663.
  • Rudelson, M. Random vectors in the isotropic position. J. Funct. Anal. 164 (1999), no. 1, 60--72. MR1694526
  • Reid, Mark D.; Williamson, Robert C. Information, divergence and risk for binary experiments. J. Mach. Learn. Res. 12 (2011), 731--817. MR2786911
  • Talagrand, Michel. A new look at independence. Ann. Probab. 24 (1996), no. 1, 1--34. MR1387624
  • Tropp, Joel A. Freedman's inequality for matrix martingales. Electron. Commun. Probab. 16 (2011), 262--270. MR2802042
  • Tropp, Joel A. Improved analysis of the subsampled randomized Hadamard transform. Adv. Adapt. Data Anal. 3 (2011), no. 1-2, 115--126. MR2835584
  • Tropp, Joel A. User-friendly tail bounds for sums of random matrices. Found. Comput. Math. 12 (2012), no. 4, 389--434. MR2946459
  • J. A. Tropp. User-friendly tools for random matrices: An introduction. Available at rlusers.cms.caltech.edu/~jtropp/notes/Tro12-User-Friendly-Tools-NIPS.pdf, Dec. 2012.
  • Voiculescu, Dan. Free entropy. Bull. London Math. Soc. 34 (2002), no. 3, 257--278. MR1887698


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.