Matrix Concentration for Expander Walks

Seminar | September 13 | 3:10-4 p.m. | 1011 Evans Hall

 Nikhil Srivastava, UC Berkeley

 Department of Statistics

We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on a Markov chain with spectral gap, confirming a conjecture of Wigderson and Xiao up to logarithmic factors in the deviation parameter. Our proof is based on a recent multi-matrix extension of the Golden-Thompson inequality due to Sutter et al. discovered in the context of quantum information theory.

Joint work with Ankit Garg (Microsoft Research New England)