User-Friendly Tail Bounds for Sums of Random Matrices
- Creators
-
Tropp, Joel A.
Abstract
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.
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.Attached Files
Accepted Version - Caltech_ACM_TR_2010_01.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:bdeae0ed676fbf24817084ba2bacf232
|
630.6 kB | Preview Download |
Additional details
- Eprint ID
- 27190
- Resolver ID
- CaltechAUTHORS:20111012-112125900
- 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
-
2019-10-03Created from EPrint's last_modified field
- Caltech groups
- Applied & Computational Mathematics
- Series Name
- ACM Technical Reports
- Series Volume or Issue Number
- 2010-01