Nearly optimal stochastic approximation for online principal subspace estimation  

作　　者：Xin Liang Zhen-Chen Guo Li Wang Ren-Cang Li Wen-Wei Lin 

机构地区：[1]Yau Mathematical Sciences Center,Tsinghua University,Beijing 100084,China [2]Yanqi Lake Beijing Institute of Mathematical Sciences and Applications,Beijing 101408,China [3]Department of Mathematics,Nanjing University,Nanjing 210093,China [4]Department of Mathematics,University of Texas at Arlington,Arlington,TX 76019,USA [5]Department of Mathematics,Hong Kong Baptist University,Hong Kong,China [6]Nanjing Center for Applied Mathematics,Nanjing 211135,China [7]Department of Applied Mathematics,Yang Ming Chiao Tung University,Hsinchu 300,China

出　　处：《Science China Mathematics》2023年第5期1087-1122,共36页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant No.11901340);National Science Foundation of USA(Grant Nos.DMS-1719620 and DMS-2009689);the ST Yau Centre at the Yang Ming Chiao Tung University.

摘　　要：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 assumptions 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.

关 键 词：principal component analysis principal component subspace stochastic approximation high-dimensional data online algorithm nite-sample analysis 

分 类 号：O212.1[理学—概率论与数理统计]