The Hoeffding inequality holds for semidefinitely upper bounded matrices

Probability and Statistics 1 Minute

You need to know: Matrix, self-adjoint matrix, eigenvalues \lambda_1, \dots, \lambda_d of d \times d matrix, notation ||A|| for the norm ||A||=\max\limits_{i}|\lambda_i| of self-adjoint matrix A, positive semidefinite matrix (one with all \lambda_i \geq 0), notation A \preceq B if matrix B-A is positive semidefinite,  probability {\mathbb P}, independence, expectation {\mathbb E}.

Background: Consider a finite sequence A_1, \dots, A_n of fixed self-adjoint d \times d matrices. Denote \sigma^2 = ||\sum\limits_{k=1}^n A_k^2||.  Let X_1, \dots, X_n be a sequence of independent, random, self-adjoint d \times d matrices satisfying {\mathbb E}[X_k]=0 and X_k \preceq A_k almost surely.

The Theorem: On 25th April 2010, Joel Tropp submitted to arxiv a paper in which he proved that, for X_1, \dots, X_n as above, and for all t \geq 0, {\mathbb P}\left(\lambda_{\text{max}}\left(\sum\limits_{k=1}^n X_k\right)\geq t\right) \leq d \cdot e^{-t^2/8\sigma^2}.

Short context: There are many classical inequalities which allows to bound the probability that the sum of independent random variables exceeds some threshold. For many applications, it is important to have a similar result for sum of matrices, where we bound the size of maximal eigenvalue \lambda_{\text{max}} of the sum. The Theorem provides a matrix version of the classical Hoeffding inequality. In the same paper, many other classical inequalities are extended to the matrix setting as well.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment