Tail inequalities for sums of random matrices that depend on the intrinsic dimension

Abstract

This work provides exponential tail inequalities for sums of random matrices that depend only on intrinsic dimensions rather than explicit matrix dimensions. These tail inequalities are similar to the matrix versions of the Chernoff bound and Bernstein inequality except with the explicit matrix dimensions replaced by a trace quantity that can be small even when the explicit dimensions are large or infinite. Some applications to covariance estimation and approximate matrix multiplication are given to illustrate the utility of the new bounds.