Distributed PCA and k-Means Clustering

This paper proposes a distributed PCA algorithm, with the theoretical guarantee that any good approximation solution on the projected data for k-means clustering is also a good approximation on the original data, while the projected dimension required is independent of the original dimension. When combined with the dis-tributed coreset-based clustering approach in [3], this leads to an algorithm in which the number of vectors communicated is independent of the size and the di-mension of the original data. Our experiment results demonstrate the effectiveness of the algorithm.