A Caltech Library Service

User-friendly Tail Bounds for Matrix Martingales

Tropp, Joel A. (2011) User-friendly Tail Bounds for Matrix Martingales. ACM Technical Reports, 2011-01. California Institute of Technology , Pasadena, CA. (Unpublished)

PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This report presents probability inequalities for sums of adapted sequences of 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. The methods also specialize to sums of independent random matrices.

Item Type:Report or Paper (Technical Report)
Tropp, Joel A.0000-0003-1024-1791
Additional Information:Date: 25 April 2010. Revised on 15 June 2010, 10 August 2010, 14 November 2010, and 16 January 2011. Research supported by ONR award N00014-08-1-0883, DARPA award N66001-08-1-2065, and AFOSR award FA9550-09-1-0643. I would like to thank Vern Paulsen and Bernhard Bodmann for some helpful conversations connected with this project. Klas Markström and David Gross provided some references to related work. Roberto Oliveira introduced me to Freedman’s inequality and encouraged me to apply the methods in the paper [Tro10c] to this problem. It was Oliveira’s elegant work [Oli10b] on matrix probability inequalities that spurred me to pursue this project in the first place. Finally, I would like to thank Yao-Liang Yu, who pointed out an inconsistency in the proof of Theorem 2.3 and who proposed the argument in Lemma 4.3. Richard Chen and Alex Gittens have also helped me root out typographic errors.
Group:Applied & Computational Mathematics
Funding AgencyGrant Number
Subject Keywords:Discrete-time martingale, large deviation, probability inequality, random matrix, sum of independent random variables.
Series Name:ACM Technical Reports
Issue or Number:2011-01
Classification Code:2010 Mathematics Subject Classification. Primary: 60B20. Secondary: 60F10, 60G50, 60G42.
Record Number:CaltechAUTHORS:20111012-114710310
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27194
Deposited On:19 Oct 2011 21:08
Last Modified:26 Aug 2022 20:56

Repository Staff Only: item control page