Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
De Huang;Jonathan Niles-Weed;Rachel A. Ward
中科院分区：
文献类型：
--
作者：
De Huang;Jonathan Niles-Weed;Rachel A. Ward
我们分析Oja的算法流$k$-PCA，并证明它达到性能接近匹配的最佳离线算法。如果能得到一系列的身份识别。$d \times d$对称矩阵，我们表明，Oja的算法可以获得一个准确的近似的子空间的顶部$k$特征向量的期望使用一些样本，规模与$d$的多项式。以前，这样的结果仅在更新具有排名1的情况下才知道。我们的分析是基于最近开发的矩阵浓度工具，这使我们能够证明强边界的随机矩阵的尾部出现在算法的执行过程中。
We analyze Oja's algorithm for streaming $k$-PCA and prove that it achieves performance nearly matching that of an optimal offline algorithm. Given access to a sequence of i.i.d. $d \times d$ symmetric matrices, we show that Oja's algorithm can obtain an accurate approximation to the subspace of the top $k$ eigenvectors of their expectation using a number of samples that scales polylogarithmically with $d$. Previously, such a result was only known in the case where the updates have rank one. Our analysis is based on recently developed matrix concentration tools, which allow us to prove strong bounds on the tails of the random matrices which arise in the course of the algorithm's execution.