Optimal principal component analysis in distributed and streaming models

Christos Boutsidis, David P. Woodruff, Peilin Zhong

2016 · 90 citations · 43 references

Concepts

Abstract

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.

References

43