Improved Distributed Principal Component Analysis
Improved Distributed Principal Component Analysis
复制标题
DOI：
--
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Yingyu Liang;Maria-Florina Balcan;Vandana Kanchanapally;David P. Woodruff
中科院分区：
文献类型：
--
作者：
Yingyu Liang;Maria-Florina Balcan;Vandana Kanchanapally;David P. Woodruff
我们研究分布式计算设置，其中有多个服务器，每个服务器都有一组点，它们希望在其点集的并集上计算函数。此设置中的一个关键任务是主成分分析 (PCA)，其中服务器希望计算一个低维子空间，捕获尽可能多的点集并集的方差。给定一个近似 PCA 的过程，我们可以用它来近似解决 k 均值聚类和低秩近似等问题。近似分布式 PCA 算法的基本属性是其通信成本和下游应用中给定所需精度的计算效率。我们为分布式 PCA 提供新的算法和分析，从而改善 k 均值聚类和相关问题的通信和计算成本。我们对现实世界数据的实证研究表明，速度提高了几个数量级，在保持通信的同时，解决方案质量的下降几乎可以忽略不计。我们开发的一些技术，例如从恒定成功概率子空间嵌入到具有独立于成功概率的维度和稀疏性的高成功概率子空间嵌入的一般转换，可能具有独立的兴趣。
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 a general transformation from a constant success probability subspace embedding to a high success probability subspace embedding with a dimension and sparsity independent of the success probability, may be of independent interest.