Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 19, 2011 | Accepted Version
Report Open

User-friendly Tail Bounds for Matrix Martingales

Abstract

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.

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.

Attached Files

Accepted Version - Caltech_ACM_TR_2011_01.pdf

Files

Caltech_ACM_TR_2011_01.pdf
Files (508.8 kB)
Name Size Download all
md5:42cbaac998645a3f0f26894718f7258d
508.8 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024