Nearly optimal stochastic approximation for online principal subspace estimation
Nearly optimal stochastic approximation for online principal subspace estimation
复制标题
在线主子空间估计的近乎最优随机逼近
DOI：
10.1007/s11425-021-1972-5
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Wen-Wei Lin
中科院分区：
文献类型：
--
作者：
Xin Liang;Zhen-Chen Guo;Li Wang;Ren-Cang Li;Wen-Wei Lin
主成分分析（PCA）在高维数据分析中得到了广泛的应用。它通过正交变换将一组可能相关的变量的观测数据点转换为一组线性不相关的变量。为了处理流数据并降低PCA的复杂性，提出了（子空间）在线PCA迭代，通过每次获取一个观察数据点来迭代更新正交变换。现有的工作（子空间）在线PCA迭代的收敛性主要集中在样本几乎必然一致有界的情况下。本文在更实际的假设下，分析了子空间在线PCA迭代的收敛性，得到了一个近似最优的有限样本误差界。我们的收敛速度几乎匹配极大极小信息的下限。我们证明了在这个意义上，子空间在线PCA迭代收敛的随机初始猜测的高概率收敛的收敛性是近全局的。这项工作也导致了一个简单的证明，最近的工作分析在线PCA的第一个主成分。
Principal component analysis (PCA) has been widely used in analyzing high-dimensional data. It converts a set of observed data points of possibly correlated variables into a set of linearly uncorrelated variables via an orthogonal transformation. To handle streaming data and reduce the complexities of PCA, (subspace) online PCA iterations were proposed to iteratively update the orthogonal transformation by taking one observed data point at a time. Existing works on the convergence of (subspace) online PCA iterations mostly focus on the case where the samples are almost surely uniformly bounded. In this paper, we analyze the convergence of a subspace online PCA iteration under more practical assumption and obtain a nearly optimal finite-sample error bound. Our convergence rate almost matches the minimax information lower bound. We prove that the convergence is nearly global in the sense that the subspace online PCA iteration is convergent with high probability for random initial guesses. This work also leads to a simpler proof of the recent work on analyzing online PCA for the first principal component only.
登录
查看更多内容
DOI：
--
发表时间：
2013-07
期刊：
--
影响因子：
--
作者：
R. Arora;Andrew Cotter;N. Srebro
通讯作者：
R. Arora;Andrew Cotter;N. Srebro
DOI：
10.1017/cbo9780511840371
发表时间：
1991
期刊：
--
影响因子：
--
作者：
R. Horn;Charles R. Johnson
通讯作者：
R. Horn;Charles R. Johnson
DOI：
10.1007/978-1-4757-2545-2
发表时间：
1996-03
期刊：
--
影响因子：
--
作者：
T. Mikosch;A. Vaart;J. Wellner
通讯作者：
T. Mikosch;A. Vaart;J. Wellner
DOI：
10.1002/9780470316559
发表时间：
1982
期刊：
--
影响因子：
--
作者：
R. Muirhead
通讯作者：
R. Muirhead
影响因子：
1.9
作者：
OJA, E
通讯作者：
OJA, E