CaltechAUTHORS
  A Caltech Library Service

Tail Bounds for All Eigenvalues of a Sum of Random Matrices

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:20140828-084239607

[img]
Preview
PDF - Submitted Version
See Usage Policy.

551Kb

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

Abstract

This work introduces the minimax Laplace transform method, a modification of the cumulant-based matrix Laplace transform method developed in [Tro11c] that yields both upper and lower bounds on each eigenvalue of a sum of random self-adjoint 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 coherence-like 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:
URLURL TypeDescription
http://arxiv.org/abs/1104.4513arXivUNSPECIFIED
ORCID:
AuthorORCID
Tropp, Joel A.0000-0003-1024-1791
Additional Information:Research supported by ONR awards N00014-08-1-0883 and N00014-11-1-0025, AFOSR award FA9550-09-1-0643, and a Sloan Fellowship.
Group:Applied & Computational Mathematics
Funders:
Funding AgencyGrant Number
ONR00014-08-1-0883
ONRN00014-11-1-0025
AFOSRFA9550-09-1-0643
Sloan FellowshipUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Applied & Computational Mathematics Technical Report2014-02
Record Number:CaltechAUTHORS:20140828-084239607
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20140828-084239607
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