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

By Daniel J. Hsu, Sham M. Kakade, Tong Zhang. 2012

76 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Electrical and Electronic Engineering, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Electrical and Electronic Engineering

In Statistics and Probability

Citations in the corpus

Spectral Methods for Indian Buffet Process Inference (2014, background): “Whenever the statistics are unbounded, concentration of moment bounds are less trivial and require the use of subgaussian and gaussian inequalities [22].”
Random Design Analysis of Ridge Regression (2011, unknown): “Lemma 10 (Matrix Bernstein bound [12]) Let X be a random matrix, and r > 0, v > 0, and k > 0 be such that, almost surely, E[X ] = 0, λmax[X ] ≤ r, λmax[E[X(2)]] ≤ v, tr(E[X2]) ≤ vk.”
Matrix concentration inequalities via the method of exchangeable pairs (2012, background): “Previous authors have applied deep results from matrix analysis to accomplish this bound: the Golden–Thompson inequality is central to [1, 35, 36], while Lieb’s result [26], Theorem 6, animates [20, 48, 49].”
An Introduction to Matrix Concentration Inequalities (2015, unknown): “Over the last few years, there have been some refinements to the basic matrix concentration bounds that improve the dependence on dimension [91, 130].”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, unknown): “proportional ti, where ti ≥ ‖Mi‖(2)2 for all i [27].”
On Some Extensions of Bernstein's Inequality for Self-adjoint Operators (2011, background): “r-valued Bernstein’s inequality Several relevant applications of the bounds that depend on the eective rank, such as covariance estimation and approximate matrix multiplication, were demonstrated in [HKZ12]. Our bounds apply in those examples as well and yield slightly sharper tails. We demonstrate ”