Optimal principal component analysis in distributed and streaming models

DOI10.1145/2897518.2897646MaRDI QIDQ5361833zbMATH OpenOpenAlexWikidataFDO

Authors Christos Boutsidis, David P. Woodruff, Peilin Zhong

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.06729

zbMATH Keywords

column subset selectiondistributed model of computationlow-rank matrix decompositionlower boundsprincipal component analysissingular value decompositionsparse matrixstreaming model of computation

Mathematics Subject Classification ID

Factorization of matrices (15A23) Factor analysis and principal components; correspondence analysis (62H25) Orthogonalization in numerical linear algebra (65F25) Computational methods for sparse matrices (65F50) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

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

Recommendations

• Numerical linear algebra in the streaming model
• Randomized algorithms for distributed computation of principal component analysis and singular value decomposition
• Distributed estimation of principal eigenspaces
• Online principal components analysis
• A randomized algorithm for principal component analysis

Cited in

(16)

• Pass-efficient methods for compression of high-dimensional turbulent flow data
• Distributed estimation of principal eigenspaces
• Practical sketching algorithms for low-rank matrix approximation
• scientific article; zbMATH DE number 7049775 (Why is no real title available?)
• Randomized sketching algorithms for low-memory dynamic optimization
• Communication-efficient distributed covariance sketch, with application to distributed PCA
• Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
• Tight query complexity lower bounds for PCA via finite sample deformed Wigner law
• Streaming low-rank matrix approximation with an application to scientific simulation
• Randomized numerical linear algebra: Foundations and algorithms
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• Training multi-layer over-parametrized neural network in subquadratic time
• Optimal subset selection for distributed local principal component analysis
• Training (overparametrized) neural networks in near-linear time
• A very sketchy talk (invited talk)
• Almost optimal superconstant-pass streaming lower bounds for reachability

This page was built for publication: Optimal principal component analysis in distributed and streaming models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361833)