Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 19, 2011 | Accepted Version
Report Open

User-Friendly Tail Bounds for Sums of Random Matrices

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

Caltech_ACM_TR_2010_01.pdf
Files (630.6 kB)
Name Size Download all
md5:bdeae0ed676fbf24817084ba2bacf232
630.6 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024