Matrix Concentration for Expander Walks
Seminar | September 13 | 3:10-4 p.m. | 1011 Evans Hall
Nikhil Srivastava, UC Berkeley
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)