Gittens, Alex A. and Tropp, Joel A.
(2011)
Tail Bounds for All Eigenvalues of a Sum of Random Matrices.
California Institute of Technology
, Pasadena, CA.
(Unpublished)
http://resolver.caltech.edu/CaltechAUTHORS:20140828084239607
Preview 

PDF
 Submitted Version
See Usage Policy.
551Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20140828084239607
Abstract
This work introduces the minimax Laplace transform method, a modification of the cumulantbased matrix Laplace transform method developed in [Tro11c] that yields both
upper and lower bounds on each eigenvalue of a sum of random selfadjoint matrices. This machinery is used
to derive eigenvalue analogs of the classical Chernoff, Bennett, and Bernstein bounds.
Two examples demonstrate the efficacy of the minimax Laplace transform. The first concerns the effects of column sparsification on the spectrum of a matrix with orthonormal rows. Here, the behavior of the singular values can be described in terms of coherencelike quantities. The second
example addresses the question of relative accuracy in the estimation of eigenvalues of the covariance
matrix of a random process. Standard results on the convergence of sample covariance matrices
provide bounds on the number of samples needed to obtain relative accuracy in the spectral norm, but these results only guarantee relative accuracy in the estimate of the maximum eigenvalue. The minimax Laplace transform argument establishes that if the lowest eigenvalues decay sufficiently fast, Ω(ε^(2)κ^2_ℓ ℓ log p) samples, where κ_ℓ = λ_1(C)/λ_ℓ(C), are sufficient to ensure that the dominant ℓ eigenvalues of the covariance matrix of a N(0,C) random vector are estimated to within a factor of 1 ± ε with high probability.
Item Type:  Report or Paper (Technical Report) 

Related URLs:  

ORCID:  

Additional Information:  Research supported
by ONR awards N000140810883 and N000141110025, AFOSR award FA95500910643, and a Sloan Fellowship. 

Group:  Applied & Computational Mathematics 

Funders:  Funding Agency  Grant Number 

ONR  000140810883  ONR  N000141110025  AFOSR  FA95500910643  Sloan Fellowship  UNSPECIFIED 


Other Numbering System:  Other Numbering System Name  Other Numbering System ID 

Applied & Computational Mathematics Technical Report  201402 


Record Number:  CaltechAUTHORS:20140828084239607 

Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:20140828084239607 

Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 

ID Code:  49011 

Collection:  CaltechACMTR 

Deposited By: 
Sydney Garstang


Deposited On:  29 Aug 2014 20:47 

Last Modified:  06 Mar 2015 22:42 

Repository Staff Only: item control page