Distributed Principal Subspace Analysis for Partitioned Big Data: Algorithms, Analysis, and Implementation
Distributed Principal Subspace Analysis for Partitioned Big Data: Algorithms, Analysis, and Implementation
复制标题
DOI：
10.1109/tsipn.2021.3122297
复制
发表时间：
2021-03
影响因子：
3.2
通讯作者：
Arpita Gang;Bingqing Xiang;W. Bajwa
中科院分区：
文献类型：
--
作者：
Arpita Gang;Bingqing Xiang;W. Bajwa
主子空间分析（PSA）-及其兄弟，主成分分析（PCA）-是信号处理和机器学习中最流行的降维方法之一。但是，集中式PSA/PCA解决方案在现代大数据时代迅速变得无关紧要，其中样本的数量和/或样本的维度通常超过单个机器的存储和/或计算能力。这导致了对分布式PSA/PCA解决方案的研究，其中数据被划分到多台机器上，并且通过机器之间的协作获得主子空间的估计。正是在这种情况下，本文重新访问的分布式PSA/PCA的一般框架下的任意连接的网络的机器，缺乏一个中央服务器的问题。本文件在这方面的主要贡献有三个方面。首先，本文提出了两种算法，可用于分布式PSA/PCA，一种是在数据划分的情况下跨样本和其他的情况下，数据划分跨（原始）功能。其次，在样本划分数据的情况下，分析了所提出的算法及其变形，并证明了它们以线性速率收敛于真子空间。第三，在合成数据和真实数据上进行了大量的实验，以验证所提出的算法的有效性。特别是，在样本明智的分区数据的情况下，基于MPI的分布式实现进行研究网络拓扑结构和通信成本之间的相互作用，以及研究所提出的算法上的落后机器的影响。
Principal Subspace Analysis (PSA)—and its sibling, Principal Component Analysis (PCA)—is one of the most popular approaches for dimensionality reduction in signal processing and machine learning. But centralized PSA/PCA solutions are fast becoming irrelevant in the modern era of Big Data, in which the number of samples and/or the dimensionality of samples often exceed the storage and/or computational capabilities of individual machines. This has led to the study of distributed PSA/PCA solutions, in which the data are partitioned across multiple machines and an estimate of the principal subspace is obtained through collaboration among the machines. It is in this vein that this paper revisits the problem of distributed PSA/PCA under the general framework of an arbitrarily connected network of machines that lacks a central server. The main contributions of the paper in this regard are threefold. First, two algorithms are proposed in the paper that can be used for distributed PSA/PCA, with one in the case of data partitioned across samples and the other in the case of data partitioned across (raw) features. Second, in the case of sample-wise partitioned data, the proposed algorithm and a variant of it are analyzed, and their convergence to the true subspace at linear rates is established. Third, extensive experiments on both synthetic and real-world data are carried out to validate the usefulness of the proposed algorithms. In particular, in the case of sample-wise partitioned data, an MPI-based distributed implementation is carried out to study the interplay between network topology and communications cost as well as to study the effects of straggler machines on the proposed algorithms.