Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Ailon, B. Chazelle, The fast Johnson–Lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput. 39(1), 302–322 (2009).
D. Achlioptas, F. McSherry, Fast computation of low-rank matrix approximations, J. Assoc. Comput. Mach. 54(2), Article 10 (2007) (electronic).
R. Ahlswede, A. Winter, Strong converse for identification via quantum channels, IEEE Trans. Inf. Theory 48(3), 569–579 (2002).
R. Bhatia, Matrix Analysis. Graduate Texts in Mathematics, vol. 169 (Springer, Berlin, 1997), p. 10.
R. Bhatia, Positive Definite Matrices (Princeton Univ. Press, Princeton, 2007).
V. Bogdanov, Gaussian Measures (American Mathematical Society, Providence, 1998).
A. Buchholz, Operator Khintchine inequality in non-commutative probability, Math. Ann. 319, 1–16 (2001).
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).
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).
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).
E. Candès, J.K. Romberg, Sparsity and incoherence in compressive sampling, Inverse Probl. 23(3), 969–985 (2007).
V.H. de la Peña, E. Giné, Decoupling: From Dependence to Independence, Probability and Its Applications (Springer, Berlin, 2002).
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.
A. Dembo, O. Zeitouni, Large Deviations: Techniques and Applications, 2nd edn. (Springer, Berlin, 1998).
E.G. Effros, A matrix convexity approach to some celebrated quantum inequalities, Proc. Natl. Acad. Sci. USA 106(4), 1006–1008 (2009).
H. Epstein, Remarks on two theorems of E. Lieb, Commun. Math. Phys. 31, 317–325 (1973).
D.A. Freedman, On tail probabilities for martingales, Ann. Probab. 3(1), 100–118 (1975).
Y. Gordon, Some inequalities for Gaussian processes and applications, Isr. J. Math. 50(4), 265–289 (1985).
Y. Gordon, Majorization of Gaussian processes and geometric applications, Probab. Theory Relat. Fields 91(2), 251–267 (1992).
D. Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inf. Theory 57(3), 1548–1566 (2011).
N.J. Higham, Functions of Matrices: Theory and Computation (Society for Industrial and Applied Mathematics, Philadelphia, 2008).
R.A. Horn, C.R. Johnson, Matrix Analysis (Cambridge Univ. Press, Cambridge, 1985).
R.A. Horn, C.R. Johnson, Topics in Matrix Analysis (Cambridge Univ. Press, Cambridge, 1994).
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).
F. Hansen, G.K. Pedersen, Jensen’s operator inequality, Bull. Lond. Math. Soc. 35, 553–564 (2003).
M. Junge, Q. Xu, On the best constants in some non-commutative martingale inequalities, Bull. Lond. Math. Soc. 37, 243–253 (2005).
M. Junge, Q. Xu, Noncommutative Burkholder/Rosenthal inequalities II: Applications, Isr. J. Math. 167, 227–282 (2008).
R. Latała, Some estimates of norms of random matrices, Proc. Am. Math. Soc. 133(5), 1273–1282 (2005).
E.H. Lieb, Convex trace functions and the Wigner–Yanase–Dyson conjecture, Adv. Math. 11, 267–288 (1973).
G. Lindblad, Expectations and entropy inequalities for finite quantum systems, Commun. Math. Phys. 39, 111–119 (1974).
F. Lust-Piquard, Inégalités de Khintchine dans C p (1<p<∞), C. R. Math. Acad. Sci. Paris 303(7), 289–292 (1986).
F. Lust-Piquard, G. Pisier, Noncommutative Khintchine and Paley inequalities, Ark. Mat. 29(2), 241–260 (1991).
M. Ledoux, M. Talagrand, Probability in Banach Spaces: Isoperimetry and Processes (Springer, Berlin, 1991).
G. Lugosi, Concentration-of-measure inequalities (2009), Available at http://www.econ.upf.edu/~lugosi/anu.pdf.
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).
C. McDiarmid, Concentration, in Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms and Combinatorics, vol. 16 (Springer, Berlin, 1998), pp. 195–248.
R. Motwani, P. Raghavan, Randomized Algorithms (Cambridge Univ. Press, Cambridge, 1995).
A. Nemirovski, Sums of random symmetric matrices and quadratic optimization under orthogonality constraints, Math. Program., Ser. B 109, 283–317 (2007).
R.I. Oliveira, Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2010), arXiv:0911.0600.
R.I. Oliveira, Sums of random Hermitian matrices and an inequality by Rudelson, Electron. Commun. Probab. 15, 203–212 (2010).
B.N. Parlett, The Symmetric Eigenvalue Problem. Classics in Applied Mathematics, vol. 20 (Society for Industrial and Applied Mathematics, Philadelphia, 1987).
V.I. Paulsen, Completely Bounded Maps and Operator Algebras. Cambridge Studies in Advanced Mathematics, vol. 78 (Cambridge Univ. Press, Cambridge, 2002).
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.
G. Pisier, Introduction to Operator Spaces (Cambridge Univ. Press, Cambridge, 2003).
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.
M. Rudelson, Random vectors in the isotropic position, J. Funct. Anal. 164, 60–72 (1999).
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).
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.
Y. Seginer, The expected norm of random matrices, Comb. Probab. Comput. 9, 149–166 (2000).
A.M.-C. So, Moment inequalities for sums of random matrices and their applications in optimization, Math. Prog. Ser. A (2009) (electronic).
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).
N. Tomczak-Jaegermann, The moduli of smoothness and convexity and the Rademacher averages of trace classes S p (1≤p<∞), Stud. Math. 50, 163–182 (1974).
J.A. Tropp, On the conditioning of random subdictionaries, Appl. Comput. Harmon. Anal. 25, 1–24 (2008).
J.A. Tropp, Improved analysis of the subsampled randomized Hadamard transform. Adv. Adapt. Data Anal. (2010, to appear). Available at arXiv:1011.1595.
J.A. Tropp, Freedman’s inequality for matrix martingales, Electron. Commun. Probab. 16, 262–270 (2011).
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.
J.A. Tropp, User-friendly tail bounds for matrix martingales, ACM Report 2011-01, California Inst. Tech., Pasadena, CA (2011).
R. Vershynin, A note on sums of independent random matrices after Ahlswede–Winter (2009), Available at http://www-personal.umich.edu/~romanv/teaching/reading-group/ahlswede-winter.pdf.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Albert Cohen.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Tropp, J.A. User-Friendly Tail Bounds for Sums of Random Matrices. Found Comput Math 12, 389–434 (2012). https://doi.org/10.1007/s10208-011-9099-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10208-011-9099-z
Keywords
- Discrete-time martingale
- Large deviation
- Probability inequality
- Random matrix
- Sum of independent random variables