mlsanityData to 7 Oct 2026

The Noisy Power Method: A Meta Algorithm with Applications

arXiv 1311.2495 ↗First posted 11 Nov 2013cs.DS cs.LGcited by 58

Not on the map. Why?

Abstract (arXiv)

We provide a new robust convergence analysis of the well-known power method for computing the dominant singular vectors of a matrix that we call the noisy power method. Our result characterizes the convergence behavior of the algorithm when a significant amount noise is introduced after each matrix-vector multiplication. The noisy power method can be seen as a meta-algorithm that has recently found a number of important applications in a broad range of machine learning problems including alternating minimization for matrix completion, streaming principal component analysis (PCA), and privacy-preserving spectral analysis. Our general analysis subsumes several existing ad-hoc convergence bounds and resolves a number of open problems in multiple applications including streaming PCA and privacy-preserving singular vector computation.

Key facts. Cited by 58 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Nov 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 7; 2023: 8; 2024: 9; 2025: 12; 2026: 10.

58 papers.

Sort:

  1. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  2. 2021Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updatescited by 21
  3. 2021DeEPCA: Decentralized Exact PCA with Linear Convergence Ratecited by 18
  4. 2021Privately Learning Subspacescited by 16
  5. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  6. 2023Share Your Representation Only: Guaranteed Improvement of the Privacy-Utility Tradeoff in Federated Learningcited by 13
  7. 2021On the Optimality of the Oja's Algorithm for Online PCAcited by 11
  8. 2021Bootstrapping the error of Oja's algorithmcited by 11
  9. 2021Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Ratescited by 10
  10. 2024Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Banditscited by 9
  11. 2021Faster Kernel Matrix Algebra via Density Estimationcited by 7
  12. 2022Statistical and Computational Trade-offs in Variational Inference: A Case Study in Inferential Model Selectioncited by 7
38 more
  1. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  2. 2023PLAN: Variance-Aware Private Mean Estimationcited by 6
  3. 2024Differentially private and decentralized randomized power methodcited by 6
  4. 2021On the Second-order Convergence Properties of Random Search Methodscited by 5
  5. 2022Fast algorithm for overcomplete order-3 tensor decompositioncited by 5
  6. 2023Streaming Kernel PCA Algorithm With Small Spacecited by 5
  7. 2023Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpointcited by 5
  8. 2021FedPower: Privacy-Preserving Distributed Eigenspace Estimationcited by 4
  9. 2022Stochastic and Private Nonconvex Outlier-Robust PCAcited by 4
  10. 2023Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasetscited by 4
  11. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  12. 2025Low-Precision Streaming PCAcited by 3
  13. 2025Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacycited by 3
  14. 2022Federated singular value decomposition for high dimensional datacited by 2
  15. 2023Learning ground states of gapped quantum Hamiltonians with Kernel Methodscited by 2
  16. 2024Spectral Guarantees for Adversarial Streaming PCAcited by 2
  17. 2024In-depth Analysis of Low-rank Matrix Factorisation in a Federated Settingcited by 2
  18. 2025On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Modelscited by 2
  19. 2021Practical and Fast Momentum-Based Power Methodscited by 1
  20. 2022Multivariate Analysis for Multiple Network Data via Semi-Symmetric Tensor PCAcited by 1
  21. 2024On Differentially Private Subspace Estimation in a Distribution-Free Settingcited by 1
  22. 2024Distributed Differentially Private Data Analytics via Secure Sketchingcited by 1
  23. 2025Decentralized Differentially Private Power Methodcited by 1
  24. 2026Adaptive Power Iteration Method for Differentially Private PCAcited by 1
  25. 2026History-aware adaptive reduced-order models via incremental singular value decompositioncited by 1
  26. 2026On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCAcited by 1
  27. 2026Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacycited by 1
  28. 2021AgFlow: Fast Model Selection of Penalized PCA via Implicit Regularization Effects of Gradient Flowcited by 0
  29. 2022Improved analysis of randomized SVD for top-eigenvector approximationcited by 0
  30. 2023Privacy-Preserving Matrix Factorization for Recommendation Systems using Gaussian Mechanismcited by 0
  31. 2023Byzantine-Resilient Federated PCA and Low Rank Column-wise Sensingcited by 0
  32. 2024Efficient Federated Low Rank Matrix Completioncited by 0
  33. 2024Investigating Privacy Leakage in Dimensionality Reduction Methods via Reconstruction Attackcited by 0
  34. 2025k-SVD with Gradient Descentcited by 0
  35. 2025Quantum EigenGame for excited state calculationcited by 0
  36. 2025AltGDmin: Alternating GD and Minimization for Partly-Decoupled (Federated) Optimizationcited by 0
  37. 2025Differentially Private and Scalable Estimation of the Network Principal Componentcited by 0
  38. 2025Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiencycited by 0

50 most cited of 58 All 58 (JSON)