A matrix expander Chernoff bound

We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to [Wigderson and Xiao 06]. Our proof is based on a new multi-matrix extension of the Golden-Thompson inequality which improves upon the inequality in [Sutter, Berta and Tomamichel 17], as well as an adaptation of an argument for the scalar case due to [Healy 08]. Our new multi-matrix Golden-Thompson inequality could be of independent interest. Secondarily, we also provide a generic reduction showing that any concentration inequality for vector-valued martingales implies a concentration inequality for the corresponding expander walk, with a weakening of parameters proportional to the squared mixing time.

Authors

• Ankit Garg 0001
• Yin Tat Lee
• Zhao Song 0002
• Nikhil Srivastava

Keywords

• derandomization
• matrix concentration
• Golden-Thompson inequality
• expander graph
• random walks
• Chernoff bound