Skip to main content.
Advanced search >
<< Back to previous page Print

<< Wednesday, September 13, 2017 >>

Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare

Matrix Concentration for Expander Walks

Seminar: Probability 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)