A Caltech Library Service

User-Friendly Tail Bounds for Sums of Random Matrices

Tropp, Joel A. (2010) User-Friendly Tail Bounds for Sums of Random Matrices. ACM Technical Reports, 2010-01. California Institute of Technology , Pasadena, CA. (Unpublished)

PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This work presents probability inequalities for sums of independent, random, self-adjoint matrices. The results frame simple, easily verifiable hypotheses on the summands, and they yield strong conclusions about the large-deviation behavior of the maximum eigenvalue of the sum. Tail bounds for the norm of a sum of rectangular matrices follow as an immediate corollary, and similar techniques yield 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 ease of use, diversity of application, and strength of conclusion that have made the scalar inequalities so valuable.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription ItemPublished Version
Tropp, Joel A.0000-0003-1024-1791
Additional Information:Date: 25 April 2010. Corrected: 29 April 2010. Research supported by ONR award N00014-08-1-0883, DARPA award N66001-08-1-2065, and AFOSR award FA9550-09-1-0643 We would like to thank Vern Paulsen and Bernhard Bodmann for some helpful conversations related to this project. We also with to thank Roberto Oliveira and Klas Markström for providing some additional references.
Group:Applied & Computational Mathematics
Funding AgencyGrant Number
Subject Keywords:Discrete-time martingale, large deviation, random matrix, sum of independent random variables.
Series Name:ACM Technical Reports
Issue or Number:2010-01
Classification Code:2010 Mathematics Subject Classification. Primary: 60B20. Secondary: 60F10, 60G50, 60G42.
Record Number:CaltechAUTHORS:20111012-112125900
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27190
Deposited On:19 Oct 2011 19:44
Last Modified:03 Oct 2019 03:21

Repository Staff Only: item control page