Tropp, Joel A. (2011) User-friendly Tail Bounds for Matrix Martingales. ACM Technical Reports, 2011-01. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20111012-114710310
![]()
|
PDF
- Accepted Version
See Usage Policy. 508kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20111012-114710310
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.
Item Type: | Report or Paper (Technical Report) | ||||||||
---|---|---|---|---|---|---|---|---|---|
ORCID: |
| ||||||||
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 | ||||||||
Funders: |
| ||||||||
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. | ||||||||
DOI: | 10.7907/62v9-yh77 | ||||||||
Record Number: | CaltechAUTHORS:20111012-114710310 | ||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20111012-114710310 | ||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||
ID Code: | 27194 | ||||||||
Collection: | CaltechACMTR | ||||||||
Deposited By: | INVALID USER | ||||||||
Deposited On: | 19 Oct 2011 21:08 | ||||||||
Last Modified: | 26 Aug 2022 20:56 |
Repository Staff Only: item control page