Research map / Learning theory and algorithms / Matrix and tensor methods
Oja's Algorithm for Streaming Sparse PCA
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that thresholding the unnormalized-then-normalized Oja vector (single pass, O(d) space, O(nd) time, random init) recovers the support of an s-sparse leading eigenvector and attains the minimax sin^2 rate O(s log d / n) under a general covariance with large effective rank.
Problem
Sparse PCA in the streaming setting: achieve the minimax sin^2 error for an s-sparse leading eigenvector with a general covariance (possibly large effective rank) using a single pass, O(d) space and O(nd) time, without strong initialization.
Approach
Run Oja's algorithm from a random Gaussian initialization and keep the k largest-magnitude entries of the Oja vector as the support estimate; then compute the eigenvector restricted to that support. A new entrywise analysis of products of random matrices projected on a random initial vector shows the support entries of the Oja vector are large while off-support entries are small, even when effecti
Key results
- Thresholded Oja vector attains sin^2 error O(s log d / n) in O(d) space and O(nd) time under a general covariance, matching the minimax lower bound up to lambda2/lambda1 and log d factors.
- Oja's full-vector error is O(r_eff/n), which is worse than the thresholded estimator when effective rank is large.
- Diagonal thresholding is shown to fail (|S ∩ Ŝ| = 0 with high probability) on a constructed covariance where small-eigenvalue support entries dominate the diagonal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Threshold the Oja vector using its largest-magnitude entries and use the recovered support for sparse PCA | Oja · General covariance sparse PCA | sin² error: O(\reff/n) -> O(s\log d/n) | Helped |
| Truncate and renormalize the Oja vector using the recovered support | Oja · Sparse PCA | sin² error: O\bb{\dfrac{\lambda_{1}}{\lambda_{1}-\lambda_{2}}}^{2}\dfrac{k\log^{2}\bb{d}}{n} | Helped |
| Restrict datapoints to the recovered support before applying OptimalOja | TruncateOja · Sparse PCA | sin² error: C''\dfrac{\lambda_{1}\lambda_{2}}{\bb{\lambda_{1}-\lambda_{2}}^{2}}\dfrac{k\log\bb{d}}{n} | Helped |
| Use diagonal thresholding to recover the support instead of Oja-based support recovery | Sparse PCA under a general covariance matrix · General covariance support recovery | support recovery probability: \mathbb{P}\bb{\left|\widehat{S} \bigcap S\right| = 0} \geq 1 - d^{-10} | Hurt |
| Use the Oja-based method rather than diagonal thresholding | Sparse PCA under a general covariance matrix · Spiked model with r=2 | sin² error | Helped |
Surprising findings
- Entries of the unnormalized Oja vector in the support do not concentrate around their expectations, while off-support entries are on average much larger than their expectations.
- Diagonal thresholding, which works for single-spike models, can fail completely on general covariances.
Limitations
- Requires a known eigengap and learning rate depending on lambda1 - lambda2, and a minimum entry magnitude condition on v1.
- Theoretical error bound is suboptimal by factors of lambda2/lambda1 and log d; sample size requirements are larger than diagonal thresholding in the spiked case.
Experimental setup
Datasets: synthetic Gaussian / subgaussian data from spiked and general covariance models
Benchmarks: synthetic covariance with n=d=1000, 100 random runs spiked model with r=2
Metrics: sin^2 error support recovery probability
Baselines: Diagonal thresholding Yang and Xu streaming truncated power method Wang and Lu online block power method SDP-based sparse PCA (D'Aspremont et al.) Oja's algorithm (full vector)
Builds on: Oja's algorithm diagonal thresholding Jain et al. 2016 accelerated stochastic power iteration geometric aggregation boosting
Closest papers by meaning
- Streaming PCA for Markovian Data (NeurIPS 2023 · similarity 0.92)
- Efficient Sparse PCA via Block-Diagonalization (ICLR 2025 · similarity 0.90)
- The Complexity of Sparse Tensor PCA (NeurIPS 2021 · similarity 0.90)
- Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features (NeurIPS 2018 · similarity 0.90)
- Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity (ICML 2025 · similarity 0.89)
- Low Precision Streaming PCA (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.