mlsanityData to 7 Oct 2026

Optimal Principal Component Analysis in Distributed and Streaming Models

arXiv 1504.06729 ↗First posted 25 Apr 2015cs.DScited by 24

Not on the map. Why?

Abstract (arXiv)

We study the Principal Component Analysis (PCA) problem in the distributed and streaming models of computation. Given a matrix A ∈ Rm × n, a rank parameter k < rank(A), and an accuracy parameter 0 < ε < 1, we want to output an m × k orthonormal matrix U for which || A - U UT A ||F2 ≤ left(1 + ε right) · || A - Ak||F2, where Ak ∈ Rm × n is the best rank-k approximation to A. This paper provides improved algorithms for distributed PCA and streaming PCA.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Apr 2015.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 4; 2022: 4; 2023: 10; 2024: 3; 2025: 3.

24 papers.

Sort:

  1. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  2. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  3. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  4. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  5. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  6. 2022Dynamic Tensor Product Regressioncited by 17
  7. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  8. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  9. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  10. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  11. 2022Low-Rank Approximation with 1/ε1/3 Matrix-Vector Productscited by 7
  12. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
12 more
  1. 2021Single Pass Entrywise-Transformed Low Rank Approximationcited by 2
  2. 2021Fast Graph Neural Tangent Kernel via Kronecker Sketchingcited by 2
  3. 2024Spectral Guarantees for Adversarial Streaming PCAcited by 2
  4. 2024Reweighted Solutions for Weighted Low Rank Approximationcited by 1
  5. 2025Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflationcited by 1
  6. 2025Connecting Parameter Magnitudes and Hessian Eigenspaces at Scale using Sketched Methodscited by 1
  7. 2022Sample Efficient Learning of Factored Embeddings of Tensor Fieldscited by 0
  8. 2023ℓp-Regression in the Arbitrary Partition Model of Communicationcited by 0
  9. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  10. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
  11. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  12. 2025Sketching Low-Rank Plus Diagonal Matricescited by 0