Improved Distributed Principal Component Analysis

We study the distributed computing setting in which there are multiple servers, each holding a set of points, who wish to compute functions on the union of their point sets. A key task in this setting is Principal Component Analysis (PCA), in which the servers would like to compute a low dimensional subspace capturing as much of the variance of the union of their point sets as possible. Given a procedure for approximate PCA, one can use it to approximately solve problems such as k-means clustering and low rank approximation. The essential properties of an approximate distributed PCA algorithm are its communication cost and computational efficiency for a given desired accuracy in downstream applications. We give new algorithms and analyses for distributed PCA which lead to improved communication and computational costs for k-means clustering and related problems. Our empirical study on real world data shows a speedup of orders of magnitude, preserving communication with only a negligible degradation in solution quality. Some of these techniques we develop, such as a general transformation from a constant success probability subspace embedding to a high success probability subspace embedding with a dimension and sparsity independent of the success probability, may be of independent interest.

• Publication year

  2014

• Venue

  Neural Information Processing Systems

• Publication date

  2014-08-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1408.5823
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• FINDING STRUCTURE WITH RANDOMNESS : PROBABILISTIC ALGORITHMS FOR CONSTRUCTING

  2016influential reference
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation

  2014cited by this paper
• Principal Component Analysis and Higher Correlations for Distributed Data

  2013cited by this paper
• Distributed k-means and k-median clustering on general communication topologies

  2013influential reference
• Combining Structured and Unstructured Randomness in Large Scale PCA

  2013cited by this paper
• Spanner: Google's globally-distributed database

  2013cited by this paper
• Relative Errors for Deterministic Low-Rank Matrix Approximations

  2013cited by this paper
• Nimble Algorithms for Cloud Computing

  2013influential reference
• Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering

  2013influential reference
• OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings

  2012influential reference
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression

  2012influential reference
• Spanner: Google's Globally-Distributed Database

  2012cited by this paper
• Low-Rank Approximation and Regression in Input Sparsity Time

  2012influential reference
• Stochastic Dimensionality Reduction for K-means Clustering

  2011cited by this paper
• A unified framework for approximating and clustering data

  2011cited by this paper
• Consensus-based distributed principal component analysis in wireless sensor networks

  2010cited by this paper
• Characterizing web-based video sharing workloads

  2009cited by this paper
• Latent Dirichlet Allocation

  2009cited by this paper
• Distributed Principal Component Analysis for Wireless Sensor

  2008cited by this paper
• Et al

  2008cited by this paper
• Distributed Principal Component Analysis for Wireless Sensor Networks

  2008cited by this paper
• Improved Approximation Algorithms for Large Matrices via Random Projections

  2006influential reference
• Principal Component Analysis for Distributed Data Sets with Updating

  2005influential reference
• Principal Component Analysis for Dimension Reduction in Massive Distributed Data Sets ∗

  2002influential reference
• Algorithms for Non-negative Matrix Factorization

  2000cited by this paper

• Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budget

  2026cites this paper
• FedFask: Fast Sketching Distributed PCA for Large-Scale Federated Data

  2025cites this paper
• Harmony-based data integration for distributed single-cell multi-omics data

  2025cites this paper
• Unified Distributed Estimation Framework for Sufficient Dimension Reduction Based on Conditional Moments

  2025cites this paper
• Reducing Transmission Cost of Distributed Principal Components Analysis in Wireless Networks With Accuracy Guaranteed

  2025cites this paper
• Multi-Agent Reinforcement Learning for Graph Discovery in D2D-Enabled Federated Learning

  2025cites this paper
• Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflation

  2025cites this paper
• FeatPCA: A feature subspace based principal component analysis technique for enhancing clustering of single-cell RNA-seq data

  2025cites this paper
• Optimal subset selection for distributed local principal component analysis

  2025cites this paper
• Discrete Speech Unit Extraction via Independent Component Analysis

  2025cites this paper
• When Green Learning Meets Federated Learning: Toward Distributed Learning with Low Complexity and Model Heterogeneity

  2024cites this paper
• Distributed Differentially Private Data Analytics via Secure Sketching

  2024cites this paper
• Distributed Clustering based on Distributional Kernel

  2024cites this paper
• Fundamental Limits of Distributed Covariance Matrix Estimation Under Communication Constraints

  2024cites this paper
• Accelerating Wireless Federated Learning via Nesterov’s Momentum and Distributed Principal Component Analysis

  2024influential citation
• Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond

  2024cites this paper
• Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search

  2024cites this paper
• Federated Supervised Principal Component Analysis

  2024cites this paper
• Accelerating Wireless Federated Learning via Nesterov's Momentum and Distributed Principle Component Analysis

  2023influential citation
• A Momentum-Based Wireless Federated Learning Acceleration With Distributed Principle Decomposition

  2023influential citation
• Share Your Representation Only: Guaranteed Improvement of the Privacy-Utility Tradeoff in Federated Learning

  2023influential citation
• On the Accelerated Noise-Tolerant Power Method

  2023cites this paper
• Scalable and Privacy-Preserving Federated Principal Component Analysis

  2023influential citation
• Distributed Sufficient Dimension Reduction for Heterogeneous Massive Data

  2023influential citation
• Communication-efficient distributed eigenspace estimation with arbitrary node failures

  2022cites this paper
• Federated horizontally partitioned principal component analysis for biomedical applications

  2022cites this paper
• Federated data processing and learning for collaboration in the physical sciences

  2022cites this paper
• A Decentralized Framework for Kernel PCA With Projection Consensus Constraints

  2022cites this paper
• Membership Inference Attack Against Principal Component Analysis

  2022cites this paper
• Federated singular value decomposition for high-dimensional data

  2022influential citation
• One-Shot Distributed Generalized Eigenvalue Problem (DGEP): Concept, Algorithm and Experiments

  2022cites this paper
• Faster Noisy Power Method

  2022influential citation
• Communication-Efficient Distributed Covariance Sketch, with Application to Distributed PCA

  2021influential citation
• EigenGame Unloaded: When playing games is better than optimizing

  2021cites this paper
• Analog MIMO Communication for One-Shot Distributed Principal Component Analysis

  2021cites this paper
• Linear expectile regression under massive data

  2021cites this paper
• Distributed Principal Component Analysis with Limited Communication

  2021cites this paper
• Streaming and Distributed Algorithms for Robust Column Subset Selection

  2021cites this paper
• Spectral vertex sparsifiers and pair-wise spanners over distributed graphs

  2021cites this paper
• Communication Efficient Distributed Hypergraph Clustering

  2021cites this paper
• Distributed Banach-Picard Iteration: Application to Distributed Parameter Estimation and PCA

  2021cites this paper
• New Aspects of Beyond Worst-Case Analysis

  2021cites this paper
• Dimensionality Reduction Methods for Brain Imaging Data Analysis

  2021cites this paper
• Riemannian geometry for restricted positive semidefinite matrices

  2021cites this paper
• Restricted Riemannian geometry for positive semidefinite matrices

  2021cites this paper
• Distributed stochastic principal component analysis using stabilized Barzilai-Borwein step-size for data compression with WSN

  2021cites this paper
• Summation pollution of principal component analysis and an improved algorithm for location sensitive data

  2021cites this paper
• Turning Channel Noise into an Accelerator for Over-the-Air Principal Component Analysis

  2021influential citation
• Federated Over-the-Air Subspace Learning from Incomplete Data

  2020cites this paper
• AI-infused Security: Robust Defense by Bridging Theory and Practice

  2020cites this paper
• Federated Over-Air Subspace Tracking From Incomplete and Corrupted Data

  2020cites this paper
• A Distributed and Secure Algorithm for Computing Dominant SVD Based on Projection Splitting

  2020cites this paper
• Design of Employee Comment Sentiment Analysis Platform Based on AE-SVM Algorithm

  2020cites this paper
• One-shot Distributed Algorithm for Generalized Eigenvalue Problem

  2020cites this paper
• Robust covariance estimation for distributed principal component analysis

  2020cites this paper
• Communication-efficient distributed eigenspace estimation

  2020cites this paper
• Communication-Efficient Distributed PCA by Riemannian Optimization

  2020influential citation
• Communication-efficient k-Means for Edge-based Machine Learning

  2020cites this paper
• Reliable Distributed Clustering with Redundant Data Assignment

  2020cites this paper
• Communication-Efficient Distributed SVD via Local Power Iterations

  2020cites this paper
• Fast and Communication-efficient Distributed Pca

  2019cites this paper
• Online Distributed Estimation of Principal Eigenspaces

  2019cites this paper
• Communication and Memory Efficient Testing of Discrete Distributions

  2019cites this paper
• The Communication Complexity of Optimization

  2019cites this paper
• Towards Optimal Moment Estimation in Streaming and Distributed Models

  2019cites this paper
• 1 Distributed Partial Clustering

  2019cites this paper
• InDP: In-Network Data Processing for Wireless Sensor Networks

  2019influential citation
• Distributed Partial Clustering

  2019cites this paper
• Federated Principal Component Analysis

  2019cites this paper
• Improved K-Means with Adaptive Divergence Weight Bat Algorithm (IKM-ADWBA) and Feature Selection for Type 2 Diabetes Mellitus Prediction

  2019cites this paper
• Dimensionality Reduction for the Sum-of-Distances Metric

  2019cites this paper
• Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition

  2019cites this paper
• Proposal Draft Beyond Worst-Case Analysis in Combinatorial Optimization

  2018cites this paper
• Differentially Private Distributed Principal Component Analysis

  2018cites this paper
• A Review of Distributed Algorithms for Principal Component Analysis

  2018cites this paper
• Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices

  2018cites this paper
• Distributed and Robust Statistical Learning

  2018cites this paper
• Fast Randomized PCA for Sparse Data

  2018cites this paper
• Minimax-Optimal Privacy-Preserving Sparse PCA in Distributed Systems

  2018cites this paper
• Distributed Statistical Estimation of Matrix Products with Applications

  2018cites this paper
• sSketch: A Scalable Sketching Technique for PCA in the Cloud

  2018cites this paper
• A Practical Algorithm for Distributed Clustering and Outlier Detection

  2018cites this paper
• Tight Bounds for Collaborative PAC Learning via Multiplicative Weights

  2018cites this paper
• Distributed optimization for Generalized Phase Retrieval Over Networks

  2018cites this paper
• The Price of Privacy for Low-rank Factorization

  2018cites this paper
• Principal Component Analysis for Big Data

  2018cites this paper
• Aggregated inference

  2018cites this paper
• N A ] 8 S ep 2 01 6 Tighter bound of Sketched Generalized Matrix Approximation

  2018cites this paper
• Distributed Differentially Private Algorithms for Matrix and Tensor Factorization

  2018cites this paper
• D ec 2 01 7 Sketching for Kronecker Product Regression and P-splines Huaian

  2018influential citation
• Faster Matrix Completion Using Randomized SVD

  2018cites this paper
• Sketching for Geometric Problems

  2017cites this paper
• Parallel Sparse Subspace Clustering via Joint Sample and Parameter Blockwise Partition

  2017cites this paper
• Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds

  2017cites this paper
• Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices

  2017cites this paper
• Sketching for Kronecker Product Regression and P-splines

  2017influential citation
• Multidataset Independent Subspace Analysis: A Framework for Analysis of Multimodal, Multi-subject Brain Imaging Data

  2017cites this paper
• Single-Pass PCA of Large High-Dimensional Data

  2017cites this paper
• Communication-Efficient Distributed Learning of Discrete Probability Distributions

  2017cites this paper
• Low rank approximation with entrywise l1-norm error

  2017cites this paper