Published October 19, 2011
| Accepted Version
Report
Open
User-friendly Tail Bounds for Matrix Martingales
- Creators
-
Tropp, Joel A.
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
- Eprint ID
- 27194
- Resolver ID
- CaltechAUTHORS:20111012-114710310
- ONR
- N00014-08-1-0883
- DARPA
- N66001-08-1-2065
- AFOSR
- FA9550-09-1-0643
- Created
-
2011-10-19Created from EPrint's datestamp field
- Updated
-
2022-08-26Created from EPrint's last_modified field
- Caltech groups
- Applied & Computational Mathematics
- Series Name
- ACM Technical Reports
- Series Volume or Issue Number
- 2011-01