Concentration Inequalities for Sums of Markov Dependent Random Matrices
Concentration Inequalities for Sums of Markov Dependent Random Matrices
复制标题
DOI：
--
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
Joe Neeman;Bobby Shi;Rachel A. Ward
中科院分区：
文献类型：
--
作者：
Joe Neeman;Bobby Shi;Rachel A. Ward
给出了由马尔可夫链产生的随机矩阵和的最大特征值的Hoeffding和bernstein型集中不等式。我们考虑一般状态空间上的时变矩阵值函数，推广了以前只考虑有限状态空间上的hoeffding型不等式和时变函数的问题。特别地，我们研究了一类非交换矩生成函数，给出了它的紧界，并用Garg等人的方法将其转化为尾界。我们的证明是频谱的，限定了一个扰动算子的范数。在此过程中，我们将动力系统和巴拿赫空间理论进行了有趣的联系，以证明力矩生成函数的极限行为的一个重要结果，这可能是独立的兴趣。
We give Hoeffding and Bernstein-type concentration inequalities for the largest eigenvalue of sums of random matrices arising from a Markov chain. We consider time-dependent matrix-valued functions on a general state space, generalizing previous that had only considered Hoeffding-type inequalities, and only for time-independent functions on a finite state space. In particular, we study a kind of noncommutative moment generating function, give tight bounds on it, and use a method of Garg et al. to turn this into tail bounds. Our proof proceeds spectrally, bounding the norm of a certain perturbed operator. In the process we make an interesting connection to dynamical systems and Banach space theory to prove a crucial result on the limiting behavior of our moment generating function that may be of independent interest.