Name
Abstract | ||
|---|---|---|
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, 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. cite{Sutter2017}, as well as an adaptation of an argument for the scalar case due to Healy cite{healy08}. 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 roughly proportional to the squared mixing time. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Probability | Discrete mathematics,Combinatorics,Martingale (probability theory),Random variable,Square (algebra),Random walk,Matrix (mathematics),Logarithm,Concentration inequality,Conjecture,Mathematics |
DocType | Volume | Citations |
Journal | abs/1704.03864 | 1 |
PageRank | References | Authors |
0.35 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ankit Garg | 1 | 125 | 16.19 |
| Nikhil Srivastava | 2 | 262 | 16.09 |