Online learning for sparse PCA in high dimensions: Exact dynamics and phase transitions

We study the dynamics of an online algorithm for learning a sparse leading eigenvector from samples generated from a spiked covariance model. This algorithm combines the classical Oja's method for online PCA with an element-wise nonlinearity at each iteration to promote sparsity. In the high-dimensional limit, the joint empirical measure of the underlying sparse eigenvector and its estimate provided by the algorithm is shown to converge weakly to a deterministic, measure-valued process. This scaling limit is characterized as the unique solution of a nonlinear PDE, and it provides exact information regarding the asymptotic performance of the algorithm. For example, performance metrics such as the cosine similarity and the misclassification rate in sparse support recovery can be obtained by examining the limiting dynamics. A steady-state analysis of the nonlinear PDE also reveals an interesting phase transition phenomenon. Although our analysis is asymptotic in nature, numerical simulations show that the theoretical predictions are accurate for moderate signal dimensions.

• Publication year

  2016

• Venue

  Information Theory Workshop

• Publication date

  2016-09-01

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1109/ITW.2016.7606821arXiv 1609.02191
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Streaming Sparse Principal Component Analysis

  2015cited by this paper
• Information-theoretically optimal sparse PCA

  2014cited by this paper
• Proximal Algorithms

  2013cited by this paper
• The Fast Convergence of Incremental PCA

  2013cited by this paper
• Stochastic optimization for PCA and PLS

  2012cited by this paper
• Sparse Principal Component Analysis and Iterative Thresholding

  2011cited by this paper
• Online Learning for Matrix Factorization and Sparse Coding

  2009cited by this paper
• Finite sample approximation results for principal component analysis: a matrix perturbation approach

  2009cited by this paper
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions

  2009cited by this paper
• Sparse principal component analysis via regularized low rank matrix approximation

  2008cited by this paper
• Generalized Power Method for Sparse Principal Component Analysis

  2008cited by this paper
• High-dimensional analysis of semidefinite relaxations for sparse principal components

  2008cited by this paper
• Sparse Principal Component Analysis

  2006cited by this paper
• Foundations of modern probability

  2004cited by this paper
• A Direct Formulation for Sparse PCA Using Semidefinite Programming

  2004cited by this paper
• A Modified Principal Component Technique Based on the LASSO

  2003cited by this paper
• On the distribution of the largest eigenvalue in principal components analysis

  2001cited by this paper
• On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix

  1985cited by this paper
• The Fokker-Planck Equation: Methods of Solution and Applications

  1984cited by this paper
• Review: P. Billingsley, Convergence of probability measures

  1971cited by this paper

• Combinatorial Sparse PCA Beyond the Spiked Identity Model

  2026cites this paper
• Towards Accurate Social User Geolocation: Mean Shift, Incremental Learning and Graph Convolutional Networks

  2025cites this paper
• A Single-loop Stochastic Riemannian ADMM for Nonsmooth Optimization

  2025cites this paper
• Implicitly Normalized Online PCA: A Regularized Algorithm with Exact High-Dimensional Dynamics

  2025influential citation
• Robust Sparse Subspace Tracking from Corrupted Data Observations

  2025cites this paper
• Learning Rate Should Scale Inversely with High-Order Data Moments in High-Dimensional Online Independent Component Analysis

  2025cites this paper
• OPIT: A Simple but Effective Method for Sparse Subspace Tracking in High-Dimension and Low-Sample-Size Context

  2024cites this paper
• Streaming First‐Order Optimization Methods With Momentum for Dominant Eigenspace Estimation

  2024cites this paper
• Oja's Algorithm for Streaming Sparse PCA

  2024cites this paper
• Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint

  2023cites this paper
• Sparse Subspace Tracking in High Dimensions

  2022cites this paper
• Stochastic Gauss–Newton Algorithms for Online PCA

  2022influential citation
• Robust Subspace Tracking Algorithms in Signal Processing: A Brief Survey

  2021cites this paper
• Low cost sparse subspace tracking algorithms

  2020cites this paper
• Online stochastic gradient descent on non-convex losses from high-dimensional inference

  2020cites this paper
• Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold

  2020cites this paper
• Detecting Extrapolation with Local Ensembles

  2019cites this paper
• Blind calibration for compressed sensing: state evolution and an online algorithm

  2019cites this paper
• Detecting Underspecification with Local Ensembles

  2019cites this paper
• Gradient-based Sparse Principal Component Analysis with Extensions to Online Learning

  2019cites this paper
• A generalization of regularized dual averaging and its dynamics

  2019cites this paper
• Streaming PCA and Subspace Tracking: The Missing Data Case

  2018cites this paper
• Subspace Estimation From Incomplete Observations: A High-Dimensional Analysis

  2018cites this paper
• A Solvable High-Dimensional Model of GAN

  2018influential citation
• Online Power Iteration For Subspace Estimation Under Incomplete Observations: Limiting Dynamics And Phase Transitions

  2018cites this paper
• Streaming Bayesian inference: Theoretical limits and mini-batch approximate message-passing

  2017cites this paper
• Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA

  2017cites this paper
• The scaling limit of high-dimensional online independent component analysis

  2017cites this paper