Nearly optimal stochastic approximation for online principal subspace estimation

DOI10.1007/S11425-021-1972-5zbMATH Open1515.65027arXiv1711.06644WikidataQ114222406 ScholiaQ114222406MaRDI QIDQ6041665FDOQ6041665

Authors:

Publication date: 12 May 2023

Published in: Science China. Mathematics (Search for Journal in Brave)

Abstract: 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 sample 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.

Full work available at URL: https://arxiv.org/abs/1711.06644

Recommendations

• Near-optimal stochastic approximation for online principal component estimation
• On the optimality of the Oja's algorithm for online PCA
• Convergence analysis of Oja's iteration for solving online PCA with nonzero-mean samples
• Online principal components analysis
• Widening the scope of an eigenvector stochastic approximation process and application to streaming PCA and related methods

zbMATH Keywords

high-dimensional dataprincipal component analysisstochastic approximationonline algorithmfinite-sample analysisprincipal component subspace

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Estimation in multivariate analysis (62H12) Numerical solutions to stochastic differential and integral equations (65C30)

Cites Work

• Weak convergence and empirical processes. With applications to statistics
• Statistics on special manifolds
• Title not available (Why is that?)
• On the largest principal angle between random subspaces
• Title not available (Why is that?)
• User-friendly tail bounds for sums of random matrices
• The special functions and their approximations. Vol. I, II
• Title not available (Why is that?)
• Title not available (Why is that?)
• Normal Multivariate Analysis and the Orthogonal Group
• A simplified neuron model as a principal component analyzer
• Minimax sparse principal subspace estimation in high dimensions
• On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix
• Near-optimal stochastic approximation for online principal component estimation
• Foundations of Data Science

Cited In (12)

• Streaming principal component analysis from incomplete data
• Convergence analysis of Oja's iteration for solving online PCA with nonzero-mean samples
• Optimal pivot path of the simplex method for linear programming based on reinforcement learning
• Title not available (Why is that?)
• Widening the scope of an eigenvector stochastic approximation process and application to streaming PCA and related methods
• Online principal components analysis
• Online Nonlinear Estimation via Iterative <inline-formula> <tex-math notation="LaTeX">$L^2$</tex-math> </inline-formula>-Space Projections: Reproducing Kernel of Subspace
• On the optimality of the Oja's algorithm for online PCA
• Stochastic Gauss-Newton algorithms for online PCA
• Online Schatten quasi-norm minimization for robust principal component analysis
• A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation
• Near-optimal stochastic approximation for online principal component estimation

This page was built for publication: Nearly optimal stochastic approximation for online principal subspace estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041665)