Concentration Inequalities for Sums of Markov Dependent Random Matrices

Abstract

We give Hoeffding and Bernstein-type concentration inequalities for the largest eigenvalue of sums of random matrices arising from a Markov chain. We consider time-dependent matrix-valued functions on a general state space, generalizing previous results that had only considered Hoeffding-type inequalities, and only for time-independent functions on a finite state space. In particular, we study a kind of noncommutative moment generating function, provide tight bounds on this object, and use a method of Garg et al. to turn this into tail bounds. Our proof proceeds spectrally, bounding the norm of a certain perturbed operator. In the process we make an interesting connection to dynamical systems and Banach space theory to prove a crucial result on the limiting behavior of our moment generating function that may be of independent interest.

References in corpus (8)

• User-friendly tail bounds for sums of random matrices
• Recovering low-rank matrices from few coefficients in any basis
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Multivariate Trace Inequalities
• Matrix concentration inequalities via the method of exchangeable pairs
• Explicit error bounds for Markov chain Monte Carlo
• Optimal Hoeffding bounds for discrete reversible Markov chains
• A Note on Element-wise Matrix Sparsification via a Matrix-valued Bernstein Inequality

Cited by in corpus (1)

• Sharp concentration for sums of matrices with Markovian dependence through universality