CaltechAUTHORS
  A Caltech Library Service

User-Friendly Tail Bounds for Sums of Random Matrices

Tropp, Joel A. (2010) User-Friendly Tail Bounds for Sums of Random Matrices. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20111012-112125900

[img]
Preview
PDF
See Usage Policy.

615Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111012-112125900

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.


Item Type:Report or Paper (Technical Report)
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.
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, random matrix, sum of independent random variables.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Applied & Computational Mathematics Technical Report2010-01
Classification Code:2010 Mathematics Subject Classification. Primary: 60B20. Secondary: 60F10, 60G50, 60G42.
Record Number:CaltechAUTHORS:20111012-112125900
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20111012-112125900
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27190
Collection:CaltechACMTR
Deposited By: Kristin Buxton
Deposited On:19 Oct 2011 19:44
Last Modified:26 Dec 2012 14:16

Repository Staff Only: item control page