nach oben

Foundations of Computational Mathematics

Erschienen in:

13.08.2021

Matrix Concentration for Products

verfasst von: De Huang, Jonathan Niles-Weed, Joel A. Tropp, Rachel Ward

Erschienen in: Foundations of Computational Mathematics | Ausgabe 6/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper develops nonasymptotic growth and concentration bounds for a product of independent random matrices. These results sharpen and generalize recent work of Henriksen–Ward, and they are similar in spirit to the results of Ahlswede–Winter and of Tropp for a sum of independent random matrices. The argument relies on the uniform smoothness properties of the Schatten trace classes.

Vorheriger Artikel Euclidean Distance Degree and Mixed Volume

Nächster Artikel Sparse Interpolation in Terms of Multivariate Chebyshev Polynomials

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

More precisely, we are considering uniformly smooth spaces whose modulus of smoothness has power type 2.

Ahlswede, R., Winter, A.: Strong converse for identification via quantum channels. IEEE Trans. Inform. Theory 48(3), 569–579 (2002). https://doi.org/10.1109/18.985947MathSciNetCrossRefMATH

Albar, W., Junge, M., Zhao, M.: Noncommutative versions of the arithmetic-geometric mean inequality (2017)

Altschuler, J.M., Parrilo, P.A.: Lyapunov exponent of rank one matrices: Ergodic formula and inapproximability of the optimal distribution (2019)

Ando, T.: Concavity of certain maps on positive definite matrices and applications to Hadamard products. Linear Algebra Appl. 26, 203–241 (1979). https://doi.org/10.1016/0024-3795(79)90179-4MathSciNetCrossRefMATH

Bai, Z., Silverstein, J.W.: Spectral analysis of large dimensional random matrices, second edn. Springer Series in Statistics. Springer, New York (2010). https://doi.org/10.1007/978-1-4419-0661-8

Ball, K., Carlen, E.A., Lieb, E.H.: Sharp uniform convexity and smoothness inequalities for trace norms. Inventiones mathematicae 115(1), 463–482 (1994). https://doi.org/10.1007/BF01231769MathSciNetCrossRefMATH

Beckner, W.: Inequalities in Fourier analysis. Ann. of Math. (2) 102(1), 159–182 (1975). https://doi.org/10.2307/1970980

Benoist, Y., Quint, J.F.: Random walks on reductive groups, vol. 62. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-47721-3

Berger, M.A.: Central limit theorem for products of random matrices. Trans. Amer. Math. Soc. 285(2), 777–803 (1984). https://doi.org/10.2307/1999463MathSciNetCrossRefMATH

10.

Bhatia, R.: Matrix analysis, Graduate Texts in Mathematics, vol. 169. Springer-Verlag, New York (1997). https://doi.org/10.1007/978-1-4612-0653-8

11.

Bonami, A.: étude des coefficients de fourier des fonctions de \(l^p(g)\). Ann. Inst. Fourier (Grenoble) 20(2), 335–402 (1970). https://doi.org/10.5802/aif.357MathSciNetCrossRefMATH

12.

Collectif: Sharp inequalities for martingales and stochastic integrals. In: Colloque Paul Lévy sur les processus stochastiques, no. 157-158 in Astérisque, pp. 75–94. Société mathématique de France (1988)

13.

Dartois, S., Forrester, P.J.: Schwinger-dyson and loop equations for a product of square ginibre random matrices. Journal of Physics A: Mathematical and Theoretical (2020). https://doi.org/10.1088/1751-8121/ab6fc4MathSciNetCrossRef

14.

Emme, J., Hubert, P.: Limit laws for random matrix products (2017)

15.

Furman, A.: Random walks on groups and random transformations. In: Handbook of dynamical systems, Vol. 1A, pp. 931–1014. North-Holland, Amsterdam (2002). https://doi.org/10.1016/S1874-575X(02)80014-5

16.

Furstenberg, H., Kesten, H.: Products of random matrices. Ann. Math. Statist. 31, 457–469 (1960). https://doi.org/10.1214/aoms/1177705909MathSciNetCrossRefMATH

17.

Gross, L.: Existence and uniqueness of physical ground states. J. Functional Analysis 10, 52–109 (1972). https://doi.org/10.1016/0022-1236(72)90057-2MathSciNetCrossRefMATH

18.

Gürbüzbalaban, M., Ozdaglar, A., Parrilo, P.: Why random reshuffling beats stochastic gradient descent. Mathematical Programming pp. 1–36 (2019). https://doi.org/10.1007/s10107-019-01440-w

19.

Hanin, B., Nica, M.: Products of many large random matrices and gradients in deep neural networks. Communications in Mathematical Physics pp. 1–36 (2019). https://doi.org/10.1007/s00220-019-03624-z

20.

Hanin, B., Paouris, G.: Non-asymptotic Results for Singular Values of Gaussian Matrix Products. arXiv e-prints arXiv:2005.08899 (2020)

21.

Henriksen, A., Ward, R.: Concentration inequalities for random matrix products (2019)

22.

Israel, A., Krahmer, F., Ward, R.: An arithmetic-geometric mean inequality for products of three matrices. Linear Algebra Appl. 488, 1–12 (2016). https://doi.org/10.1016/j.laa.2015.09.013MathSciNetCrossRefMATH

23.

Kathuria, T., Mukherjee, S., Srivastava, N.: On Concentration Inequalities for Random Matrix Products. arXiv e-prints arXiv:2003.06319 (2020)

24.

Kieburg, M.: Products of Complex Rectangular and Hermitian Random Matrices (2019)

25.

Ledoux, M., Talagrand, M.: Probability in Banach spaces. Classics in Mathematics. Springer-Verlag, Berlin (2011). https://doi.org/10.1007/978-3-642-20212-4. Isoperimetry and processes, Reprint of the 1991 edition

26.

Ledrappier, F.: Some asymptotic properties of random walks on free groups. In: Topics in probability and Lie groups: boundary theory, vol. 28, pp. 117–152. Amer. Math. Soc., Providence, RI (2001). https://doi.org/10.1007/978-3-642-20212-4

27.

Lieb, E.H.: Convex trace functions and the Wigner-Yanase-Dyson conjecture. Advances in Math. 11, 267–288 (1973). https://doi.org/10.1016/0001-8708(73)90011-XMathSciNetCrossRefMATH

28.

Lust-Piquard, F.: Inégalités de Khintchine dans \(C_p\;(1<p<\infty )\). C. R. Acad. Sci. Paris Sér. I Math. 303(7), 289–292 (1986)

29.

Naor, A.: On the banach-space-valued azuma inequality and small-set isoperimetry of alon–roichman graphs. Combinatorics, Probability and Computing 21(4), 623–634 (2012). https://doi.org/10.1017/S0963548311000757MathSciNetCrossRefMATH

30.

Nica, A., Speicher, R.: Lectures on the combinatorics of free probability, London Mathematical Society Lecture Note Series, vol. 335. Cambridge University Press, Cambridge (2006). https://doi.org/10.1017/CBO9780511735127

31.

Oja, E.: A simplified neuron model as a principal component analyzer. J. Math. Biol. 15(3), 267–273 (1982). https://doi.org/10.1007/BF00275687MathSciNetCrossRefMATH

32.

Oliveira, R.I.: Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges (2009)

33.

Pisier, G.: Martingales with values in uniformly convex spaces. Israel J. Math. 20(3-4), 326–350 (1975). https://doi.org/10.1007/BF02760337MathSciNetCrossRefMATH

34.

Rao, N.R., Edelman, A.: The polynomial method for random matrices. Found. Comput. Math. 8(6), 649–702 (2008). https://doi.org/10.1007/s10208-007-9013-xMathSciNetCrossRefMATH

35.

Recht, B., Re, C.: Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences (2012)

36.

Ricard, É., Xu, Q.: A noncommutative martingale convexity inequality. The Annals of Probability 44(2), 867–882 (2016). https://doi.org/10.1214/14-AOP990MathSciNetCrossRefMATH

37.

Shlyakhtenko, D.: Random matrices and free probability. In: Random Matrices, 26. Amer. Math. Soc., Providence, RI (2019)

38.

Speicher, R.: Lecture notes on “free probability theory” (2019)

39.

Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2), 262–278 (2009). https://doi.org/10.1007/s00041-008-9030-4MathSciNetCrossRefMATH

40.

Tomczak-Jaegermann, N.: The moduli of smoothness and convexity and the Rademacher averages of trace classes \(S_{p}(1\le p<\infty )\). Studia Math. 50, 163–182 (1974)

41.

Tropp, J.A.: Freedman’s inequality for matrix martingales. Electronic Communications in Probability 16, 262–270 (2011). https://doi.org/10.1214/ECP.v16-1624MathSciNetCrossRefMATH

42.

Tropp, J.A.: User-friendly tail bounds for sums of random matrices. Found. Comput. Math. 12(4), 389–434 (2012). https://doi.org/10.1007/s10208-011-9099-zMathSciNetCrossRefMATH

43.

Tropp, J.A.: An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning 8(1-2), 1–230 (2015). https://doi.org/10.1561/2200000048CrossRefMATH

44.

Tropp, J.A.: The expected norm of a sum of independent random matrices: an elementary approach. In: High dimensional probability VII, Progr. Probab., vol. 71, pp. 173–202. Springer, [Cham] (2016). https://doi.org/10.1007/978-3-319-40519-3_8

45.

Tropp, J.A.: Second-order matrix concentration inequalities. Appl. Comput. Harmon. Anal. 44(3), 700–736 (2018). https://doi.org/10.1016/j.acha.2016.07.005MathSciNetCrossRefMATH

46.

Tsitsiklis, J.N., Blondel, V.D.: The Lyapunov exponent and joint spectral radius of pairs of matrices are hard—when not impossible—to compute and to approximate. Math. Control Signals Systems 10(1), 31–40 (1997). https://doi.org/10.1007/BF01219774MathSciNetCrossRefMATH

47.

Tulino, A.M., Verdú, S.: Random matrix theory and wireless communications. Foundations and Trends in Communications and Information Theory 1(1), 1–182 (2004). https://doi.org/10.1561/0100000001CrossRefMATH

48.

Wilkinson, A.: What are Lyapunov exponents, and why are they interesting? Bull. Amer. Math. Soc. (N.S.) 54(1), 79–105 (2017). https://doi.org/10.1090/bull/1552

49.

Yang, G.: Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation (2019)

Titel: Matrix Concentration for Products
verfasst von: De Huang
Jonathan Niles-Weed
Joel A. Tropp
Rachel Ward
Publikationsdatum: 13.08.2021
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 6/2022
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-021-09533-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 6/2022

Tropical Bisectors and Voronoi Diagrams

Sparse Interpolation in Terms of Multivariate Chebyshev Polynomials

Robust Group Synchronization via Cycle-Edge Message Passing

Euclidean Distance Degree and Mixed Volume

Deep Composition of Tensor-Trains Using Squared Inverse Rosenblatt Transports

Premium Partner