Matrix Concentration for Expander Walks

Probability Seminar
Sep 13, 2017 3:10pm to 4:00pm
Location: 
1011 Evans Hall
Status: 
Happening As Scheduled
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...
Nikhil Srivastava, UC Berkeley