2016 · 90 citations · 43 references
ComputingComputer ScienceData ScienceAlgorithmsDistributed SystemsOptimizationDimensionality ReductionDistributed AlgorithmsDistributed ComputingDistributed Data ProcessingMatrix ComputationPrincipal Component AnalysisAccuracyLow-rank ApproximationLow-rank Matrix FactorizationPrincipal ComponentsSparse Matrix ComputationStreaming Principal Component Analysis
This paper studies 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-UUTA||2F≤(1+ε)||A-Ak||2F where Ak∈Rm×n is the best rank-k approximation to A.
43
Advances in Neural Information Processing Systems 28
Peter Flach, Meelis Kull · 2015 · 14.7K citations
Improved Approximation Algorithms for Large Matrices via Random Projections
Tamás Sarlós · 2006 · 691 citations
Low rank approximation and regression in input sparsity time
Kenneth L. Clarkson, David P. Woodruff · 2013 · 395 citations