Optimal Principal Component Analysis in Distributed and Streaming Models

Abstract

We study the Principal Component Analysis (PCA) problem in the distributed and streaming models of computation. Given a matrix $A\in R^{m\times n},$ a rank parameter $k<rank(A)$, and an accuracy parameter $0<\epsilon <1$, we want to output an $m\times k$ orthonormal matrix $U$ for which $$||A-U{U}^{T}A|{|}_F^2\le \left(1+\epsilon \right)\cdot ||A-A_k|{|}_F^2,$$ where $A_k\in R^{m\times n}$ is the best rank-$k$ approximation to $A$. This paper provides improved algorithms for distributed PCA and streaming PCA.

STOC2016 full version

References in corpus (6)

• Improved Distributed Principal Component Analysis
• Distributed Principal Component Analysis for Wireless Sensor Networks
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Low Rank Approximation and Regression in Input Sparsity Time
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Distributed Low Rank Approximation of Implicit Functions of a Matrix

Cited by in corpus (3)

• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• An Improved Gap-Dependency Analysis of the Noisy Power Method
• Effective sketching methods for value function approximation