# Optimal Principal Component Analysis in Distributed and Streaming Models

arXiv: https://arxiv.org/abs/1504.06729 · HTML: https://mlsanity.com/paper/1504.06729/

## Key facts

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

## Built on by (most cited first, 24 of 24)

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation](https://mlsanity.com/paper/2306.04169/) (2023)
- [Solving Tensor Low Cycle Rank Approximation](https://mlsanity.com/paper/2304.06594/) (2023)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Single Pass Entrywise-Transformed Low Rank Approximation](https://mlsanity.com/paper/2107.07889/) (2021)
- [Fast Graph Neural Tangent Kernel via Kronecker Sketching](https://mlsanity.com/paper/2112.02446/) (2021)
- [Spectral Guarantees for Adversarial Streaming PCA](https://mlsanity.com/paper/2408.10332/) (2024)
- [Reweighted Solutions for Weighted Low Rank Approximation](https://mlsanity.com/paper/2406.02431/) (2024)
- [Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflation](https://mlsanity.com/paper/2502.17615/) (2025)
- [Connecting Parameter Magnitudes and Hessian Eigenspaces at Scale using Sketched Methods](https://mlsanity.com/paper/2504.14701/) (2025)
- [Sample Efficient Learning of Factored Embeddings of Tensor Fields](https://mlsanity.com/paper/2209.00372/) (2022)
- [ℓp-Regression in the Arbitrary Partition Model of Communication](https://mlsanity.com/paper/2307.05117/) (2023)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming](https://mlsanity.com/paper/2310.19068/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)
- [Sketching Low-Rank Plus Diagonal Matrices](https://mlsanity.com/paper/2509.23587/) (2025)

## 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.