User-friendly tail bounds for sums of random matrices. (English) Zbl 1259.60008

Tropp, Joel A.

Found. Comput. Math. 12, No. 4, 389-434 (2012).

Summary: This paper presents new probability inequalities for sums of independent, random, self-adjoint matrices. These results place simple and easily verifiable hypotheses on the summands, and they deliver strong conclusions about the large-deviation behavior of the maximum eigenvalue of the sum. Tail bounds for the norm of a sum of random rectangular matrices follow as an immediate corollary. The proof techniques also yield some information about matrix-valued martingales.
In other words, this paper provides noncommutative generalizations of the classical bounds associated with the names Azuma, Bennett, Bernstein, Chernoff, Hoeffding, and McDiarmid. The matrix inequalities promise the same diversity of application, ease of use, and strength of conclusion that have made the scalar inequalities so valuable.

MSC:

60B20	Random matrices (probabilistic aspects)
60F10	Large deviations
60G50	Sums of independent random variables; random walks
60G42	Martingales with discrete parameter

Keywords:

discrete-time martingales; large deviation; probability inequalities; random matrices; sums of independent random variables

Software:

mftoolbox

References:

[1]	N. Ailon, B. Chazelle, The fast Johnson–Lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput. 39(1), 302–322 (2009). · Zbl 1185.68327
[2]	D. Achlioptas, F. McSherry, Fast computation of low-rank matrix approximations, J. Assoc. Comput. Mach. 54(2), Article 10 (2007) (electronic). · Zbl 1311.94031
[3]	R. Ahlswede, A. Winter, Strong converse for identification via quantum channels, IEEE Trans. Inf. Theory 48(3), 569–579 (2002). · Zbl 1071.94530
[4]	R. Bhatia, Matrix Analysis. Graduate Texts in Mathematics, vol. 169 (Springer, Berlin, 1997), p. 10. · Zbl 0863.15001
[5]	R. Bhatia, Positive Definite Matrices (Princeton Univ. Press, Princeton, 2007). · Zbl 1133.15017
[6]	V. Bogdanov, Gaussian Measures (American Mathematical Society, Providence, 1998).
[7]	A. Buchholz, Operator Khintchine inequality in non-commutative probability, Math. Ann. 319, 1–16 (2001). · Zbl 0991.46035
[8]	A. Buchholz, Optimal constants in Khintchine-type inequalities for Fermions, Rademachers and q-Gaussian operators, Bull. Pol. Acad. Sci., Math. 53(3), 315–321 (2005). · Zbl 1117.46043
[9]	H. Chernoff, A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Stat. 23(4), 493–507 (1952). · Zbl 0048.11804
[10]	D. Cristofides, K. Markström, Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales, Random Struct. Algorithms 32(8), 88–100 (2008). · Zbl 1130.05030
[11]	E. Candès, J.K. Romberg, Sparsity and incoherence in compressive sampling, Inverse Probl. 23(3), 969–985 (2007). · Zbl 1120.94005
[12]	V.H. de la Peña, E. Giné, Decoupling: From Dependence to Independence, Probability and Its Applications (Springer, Berlin, 2002).
[13]	K.R. Davidson, S. J. Szarek. Local operator theory, random matrices, and Banach spaces, in Handbook of Banach Space Geometry, ed. by W.B. Johnson, J. Lindenstrauss (Elsevier, Amsterdam, 2002), pp. 317–366. · Zbl 1067.46008
[14]	A. Dembo, O. Zeitouni, Large Deviations: Techniques and Applications, 2nd edn. (Springer, Berlin, 1998). · Zbl 0896.60013
[15]	E.G. Effros, A matrix convexity approach to some celebrated quantum inequalities, Proc. Natl. Acad. Sci. USA 106(4), 1006–1008 (2009). · Zbl 1202.81018
[16]	H. Epstein, Remarks on two theorems of E. Lieb, Commun. Math. Phys. 31, 317–325 (1973). · Zbl 0257.46089
[17]	D.A. Freedman, On tail probabilities for martingales, Ann. Probab. 3(1), 100–118 (1975). · Zbl 0313.60037
[18]	Y. Gordon, Some inequalities for Gaussian processes and applications, Isr. J. Math. 50(4), 265–289 (1985). · Zbl 0663.60034
[19]	Y. Gordon, Majorization of Gaussian processes and geometric applications, Probab. Theory Relat. Fields 91(2), 251–267 (1992). · Zbl 0744.60039
[20]	D. Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inf. Theory 57(3), 1548–1566 (2011). · Zbl 1366.94103
[21]	N.J. Higham, Functions of Matrices: Theory and Computation (Society for Industrial and Applied Mathematics, Philadelphia, 2008). · Zbl 1167.15001
[22]	R.A. Horn, C.R. Johnson, Matrix Analysis (Cambridge Univ. Press, Cambridge, 1985). · Zbl 0576.15001
[23]	R.A. Horn, C.R. Johnson, Topics in Matrix Analysis (Cambridge Univ. Press, Cambridge, 1994). · Zbl 0801.15001
[24]	N. Halko, P.-G. Martinsson, J.A. Tropp, Finding structure with randomness: stochastic algorithms for constructing approximate matrix decompositions, SIAM Rev. 53(2), 217–288 (2011). · Zbl 1269.65043
[25]	F. Hansen, G.K. Pedersen, Jensen’s operator inequality, Bull. Lond. Math. Soc. 35, 553–564 (2003). · Zbl 1051.47014
[26]	M. Junge, Q. Xu, On the best constants in some non-commutative martingale inequalities, Bull. Lond. Math. Soc. 37, 243–253 (2005). · Zbl 1088.46037
[27]	M. Junge, Q. Xu, Noncommutative Burkholder/Rosenthal inequalities II: Applications, Isr. J. Math. 167, 227–282 (2008). · Zbl 1217.46043
[28]	R. Latała, Some estimates of norms of random matrices, Proc. Am. Math. Soc. 133(5), 1273–1282 (2005). · Zbl 1067.15022
[29]	E.H. Lieb, Convex trace functions and the Wigner–Yanase–Dyson conjecture, Adv. Math. 11, 267–288 (1973). · Zbl 0267.46055
[30]	G. Lindblad, Expectations and entropy inequalities for finite quantum systems, Commun. Math. Phys. 39, 111–119 (1974). · Zbl 0294.46052
[31]	F. Lust-Piquard, Inégalités de Khintchine dans C p (1<p<, C. R. Math. Acad. Sci. Paris 303(7), 289–292 (1986).
[32]	F. Lust-Piquard, G. Pisier, Noncommutative Khintchine and Paley inequalities, Ark. Mat. 29(2), 241–260 (1991). · Zbl 0755.47029
[33]	M. Ledoux, M. Talagrand, Probability in Banach Spaces: Isoperimetry and Processes (Springer, Berlin, 1991). · Zbl 0748.60004
[34]	G. Lugosi, Concentration-of-measure inequalities (2009), Available at http://www.econ.upf.edu/\(\sim\)lugosi/anu.pdf .
[35]	P. Massart, Concentration Inequalities and Model Selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII–2003. Lecture Notes in Mathematics, vol. 1896 (Springer, Berlin, 2007). · Zbl 1170.60006
[36]	C. McDiarmid, Concentration, in Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms and Combinatorics, vol. 16 (Springer, Berlin, 1998), pp. 195–248. · Zbl 0927.60027
[37]	R. Motwani, P. Raghavan, Randomized Algorithms (Cambridge Univ. Press, Cambridge, 1995). · Zbl 0849.68039
[38]	A. Nemirovski, Sums of random symmetric matrices and quadratic optimization under orthogonality constraints, Math. Program., Ser. B 109, 283–317 (2007). · Zbl 1156.90012
[39]	R.I. Oliveira, Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2010), arXiv:0911.0600 .
[40]	R.I. Oliveira, Sums of random Hermitian matrices and an inequality by Rudelson, Electron. Commun. Probab. 15, 203–212 (2010). · Zbl 1228.60017
[41]	B.N. Parlett, The Symmetric Eigenvalue Problem. Classics in Applied Mathematics, vol. 20 (Society for Industrial and Applied Mathematics, Philadelphia, 1987). · Zbl 0885.65039
[42]	V.I. Paulsen, Completely Bounded Maps and Operator Algebras. Cambridge Studies in Advanced Mathematics, vol. 78 (Cambridge Univ. Press, Cambridge, 2002). · Zbl 1029.47003
[43]	D. Petz, A survey of certain trace inequalities, in Functional Analysis and Operator Theory. Banach Center Publications, vol. 30 (Polish Acad. Sci., Warsaw, 1994), pp. 287–298. · Zbl 0802.15012
[44]	G. Pisier, Introduction to Operator Spaces (Cambridge Univ. Press, Cambridge, 2003). · Zbl 1093.46001
[45]	B. Recht, Simpler approach to matrix completion, J. Mach. Learn. Res. (2009, to appear). Available at http://pages.cs.wisc.edu/brecht/papers/09.Recht.ImprovedMC.pdf . · Zbl 1280.68141
[46]	M. Rudelson, Random vectors in the isotropic position, J. Funct. Anal. 164, 60–72 (1999). · Zbl 0929.46021
[47]	M.B. Ruskai, Inequalities for quantum entropy: a review with conditions for equality, J. Math. Phys. 43(9), 4358–4375 (2002). Erratum: J. Math. Phys. 46(1), 0199101 (2005). · Zbl 1060.82006
[48]	M. Rudelson, R. Vershynin, Sampling from large matrices: an approach through geometric functional analysis, J. Assoc. Comput. Mach. 54(4), Article 21 (2007) (electronic) 19 pp. · Zbl 1326.68333
[49]	Y. Seginer, The expected norm of random matrices, Comb. Probab. Comput. 9, 149–166 (2000). · Zbl 0969.15009
[50]	A.M.-C. So, Moment inequalities for sums of random matrices and their applications in optimization, Math. Prog. Ser. A (2009) (electronic).
[51]	A. Sankar, D.A. Spielman, S.-H. Teng, Smoothed analysis of the condition numbers and growth factors of matrices, SIAM J. Matrix Anal. Appl. 28(2), 446–476 (2006). · Zbl 1179.65033
[52]	N. Tomczak-Jaegermann, The moduli of smoothness and convexity and the Rademacher averages of trace classes S p (1<, Stud. Math. 50, 163–182 (1974). · Zbl 0282.46016
[53]	J.A. Tropp, On the conditioning of random subdictionaries, Appl. Comput. Harmon. Anal. 25, 1–24 (2008). · Zbl 1143.15026
[54]	J.A. Tropp, Improved analysis of the subsampled randomized Hadamard transform. Adv. Adapt. Data Anal. (2010, to appear). Available at arXiv:1011.1595 .
[55]	J.A. Tropp, Freedman’s inequality for matrix martingales, Electron. Commun. Probab. 16, 262–270 (2011). · Zbl 1225.60017
[56]	J.A. Tropp, From the joint convexity of quantum relative entropy to a concavity theorem of Lieb. Proc. Amer. Math. Soc. (2011, to appear). Available at arXiv:1101.1070 . · Zbl 1455.52006
[57]	J.A. Tropp, User-friendly tail bounds for matrix martingales, ACM Report 2011-01, California Inst. Tech., Pasadena, CA (2011).
[58]	R. Vershynin, A note on sums of independent random matrices after Ahlswede–Winter (2009), Available at http://www-personal.umich.edu/\(\sim\)romanv/teaching/reading-group/ahlswede-winter.pdf .