CaltechAUTHORS
  A Caltech Library Service

User-friendly Tail Bounds for Matrix Martingales

Tropp, Joel A. (2011) User-friendly Tail Bounds for Matrix Martingales. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20111012-114710310

[img]
Preview
PDF
See Usage Policy.

496Kb

Use this Persistent URL to link to this item: http://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)
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:
Funding AgencyGrant Number
ONRN00014-08-1-0883
DARPAN66001-08-1-2065
AFOSRFA9550-09-1-0643
Subject Keywords:Discrete-time martingale, large deviation, probability inequality, random matrix, sum of independent random variables.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Applied & Computational Mathematics Technical Report2011-01
Classification Code:2010 Mathematics Subject Classification. Primary: 60B20. Secondary: 60F10, 60G50, 60G42.
Record Number:CaltechAUTHORS:20111012-114710310
Persistent URL:http://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: Kristin Buxton
Deposited On:19 Oct 2011 21:08
Last Modified:26 Dec 2012 14:16

Repository Staff Only: item control page