Improved Distributed Principal Component Analysis

Abstract

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 ${\ell }_2$-error fitting problems such as $k$-means clustering and subspace clustering. 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.

References in corpus (1)

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

Cited by in corpus (25)

• Communication Complexity of Distributed Convex Learning and Optimization
• Optimal approximate matrix product in terms of stable rank
• Distributed Differentially-Private Algorithms for Matrix and Tensor Factorization
• Federated Principal Component Analysis
• Distributed Estimation of Principal Eigenspaces
• Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis
• Principal component analysis for big data
• Single-Pass PCA of Large High-Dimensional Data
• Communication-efficient Distributed Sparse Linear Discriminant Analysis
• An Improved Gap-Dependency Analysis of the Noisy Power Method
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Distributed Partial Clustering
• Low Rank Approximation with Entrywise ${\ell }_1$-Norm Error
• A Distributed One-Step Estimator
• Tight Bounds for Collaborative PAC Learning via Multiplicative Weights
• Communication-Efficient Distributed SVD via Local Power Iterations
• Optimal Principal Component Analysis in Distributed and Streaming Models
• Analog MIMO Communication for One-shot Distributed Principal Component Analysis
• Distributed Low Rank Approximation of Implicit Functions of a Matrix
• On the Communication Complexity of Distributed Clustering
• The Price of Differential Privacy for Low-Rank Factorization
• Communication and Memory Efficient Testing of Discrete Distributions
• Multiresolution Kernel Approximation for Gaussian Process Regression
• Tighter bound of Sketched Generalized Matrix Approximation
• Online Optimization for Large-Scale Max-Norm Regularization