User-Friendly Tail Bounds for Matrix Martingales

reportActive / Technical Report | Accession Number: ADA555817 | Open PDF

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.

Author(s):
Tropp, Joel A.
Author Organization(s):
CALIFORNIA INST OF TECH PASADENA
Descriptive Note:
Technical rept.
Supplementary Note:
Sponsored in part by DARPA and AFOSR contract no. FA9550-09-1-0643. DOI: 10.21236/ADA555817
Pagination:
0015

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release
Distribution Statement:
Approved For Public Release; Distribution Is Unlimited.

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
TR-2011-01
Contract/Grant Number(s):
N00014-08-1-0883, N66001-08-1-2065
Monitor Series:
ONR
 Subject Terms
Joint Capability Areas:
JCA_5_Command and Control; JCA_5.3_Planning; JCA_1.2.5_Lessons Learned; JCA_1.2_Force Preparation; JCA_1_Force Support; JCA_8_Building Partnerships
Modernization Areas:
Quantum Science and Computing
Communities of Interest:
Energy and Power Technologies
Descriptor(s):
*INEQUALITIES, *MATRICES(MATHEMATICS), *PROBABILITY, EIGENVALUES, HILBERT SPACE, OPERATORS(MATHEMATICS), SEQUENCES(MATHEMATICS)
Field(s)/Group(s):
Numerical Mathematics
Keyword(s):
DISCRETE TIME MARTINGALE, LARGE DEVIATION, PROBABILITY INEQUALITY, RANDOM MATRIX, SUM OF INDEPENDENT RANDOM VARIABLES, MARTINGALE TECHNIQUES, RADEMACHER SERIES, GAUSSIAN SERIES, CHERNOFF MATRIX, BERNSTEIN MATRIX, BENNETT MATRIX, FREEDMAN INEQUALITY, FREEDMAN MATRIX
Report Date:
2011 Jan 16
Creation Date:
2012 Mar 14