论文标题
关于随机基质产品的浓度不平等
On Concentration Inequalities for Random Matrix Products
论文作者
论文摘要
考虑$ n $复杂随机矩阵$ x_1，\ ldots，x_n $ size $ d \ times d $采样i.i.d.从平均$ e [x] =μ$的分布中。尽管对这些矩阵的平均值的浓度进行了充分研究，但此类矩阵的其他功能的浓度尚不清楚。在随机迭代算法的背景下产生的一个功能，例如OJA的主要组件分析算法，是归一化的矩阵产品定义为$ \ prod \ limits_ {i = 1}^{n}^{n} \ left（i + \ frac {x_i} n} formentiation proporties proportiation norteriation norteriation nortial proportiation nortial proportiation nortiations proporties。 \ cite {hw19}。但是，它们的结果在对矩阵尺寸以及样品数量的依赖性方面是最佳的。在本文中，我们为此类矩阵产品提供了更强的浓度结果，该产品在$ n $和$ d $中是最佳的，而不是常数因素。我们的证明是基于考虑矩阵doob martingale，控制了该马丁莱的二次变异，并应用了tropp \ cite {troppintro15}的矩阵freedman不平等。
Consider $n$ complex random matrices $X_1,\ldots,X_n$ of size $d\times d$ sampled i.i.d. from a distribution with mean $E[X]=μ$. While the concentration of averages of these matrices is well-studied, the concentration of other functions of such matrices is less clear. One function which arises in the context of stochastic iterative algorithms, like Oja's algorithm for Principal Component Analysis, is the normalized matrix product defined as $\prod\limits_{i=1}^{n}\left(I + \frac{X_i}{n}\right).$ Concentration properties of this normalized matrix product were recently studied by \cite{HW19}. However, their result is suboptimal in terms of the dependence on the dimension of the matrices as well as the number of samples. In this paper, we present a stronger concentration result for such matrix products which is optimal in $n$ and $d$ up to constant factors. Our proof is based on considering a matrix Doob martingale, controlling the quadratic variation of that martingale, and applying the Matrix Freedman inequality of Tropp \cite{TroppIntro15}.
