A matrix expander Chernoff bound
A matrix expander Chernoff bound
复制标题
矩阵展开器切尔诺夫界
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
N. Srivastava
中科院分区：
文献类型：
--
作者：
A. Garg;Y. Lee;Zhao Song;N. Srivastava
本文证明了通过扩张器上的随机游动采样的矩阵值随机变量和的一个Bauff-type界，证实了[Wigderson和Xiao 06]的一个猜想。我们的证明是基于Golden-Thompson不等式的一个新的多矩阵扩展，它改进了[Sutter，Berta和Tomamichel 17]中的不等式，以及[Healy 08]中标量情况下的一个参数。我们的新的多矩阵Golden-Thompson不等式可能是独立的利益。其次，我们还提供了一个通用的减少表明，任何向量值鞅的浓度不等式意味着相应的扩展行走的浓度不等式，与削弱的参数成正比的平方混合时间。
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.
DOI：
10.1007/s00023-017-0569-y
发表时间：
2017
期刊：
Annales Henri Poincaré
影响因子：
--
作者：
Fumio Hiai;Robert König;Marco Tomamichel
通讯作者：
Marco Tomamichel