Timezone: »

 
Poster
Improved Distributed Principal Component Analysis
Yingyu Liang · Maria-Florina F Balcan · Vandana Kanchanapally · David Woodruff

Thu Dec 11 11:00 AM -- 03:00 PM (PST) @ Level 2, room 210D
in Poster Session »
We study the distributed computing setting in which there are multiple servers, each holding a set of points, who wish to compute functions on the union of their point sets. A key task in this setting is Principal Component Analysis (PCA), in which the servers would like to compute a low dimensional subspace capturing as much of the variance of the union of their point sets as possible. Given a procedure for approximate PCA, one can use it to approximately solve problems such as $k$-means clustering and low rank approximation. The essential properties of an approximate distributed PCA algorithm are its communication cost and computational efficiency for a given desired accuracy in downstream applications. We give new algorithms and analyses for distributed PCA which lead to improved communication and computational costs for $k$-means clustering and related problems. Our empirical study on real world data shows a speedup of orders of magnitude, preserving communication with only a negligible degradation in solution quality. Some of these techniques we develop, such as input-sparsity subspace embeddings with high correctness probability with a dimension and sparsity independent of the error probability, may be of independent interest.
[ PDF] 

Author Information

Yingyu Liang (Princeton University)
Maria-Florina F Balcan (Georgia Tech)
Vandana Kanchanapally
David Woodruff (IBM Research)

More from the Same Authors