We recently proposed an algorithmic framework, distributed Banach-Picard iteration (DBPI), allowing a set of agents linked by a communication network to find a fixed point of a map that: (a) is the average of individu...
详细信息
We recently proposed an algorithmic framework, distributed Banach-Picard iteration (DBPI), allowing a set of agents linked by a communication network to find a fixed point of a map that: (a) is the average of individual maps held by said agents;(b) is locally contractive (LC). Given such a map, DBPI yields a distributed algorithm provably inheriting the local linear convergence (LLC) of the standard Banach-Picard iteration for the centralized (average) map. Here, we instantiate DBPI in two classical problems, which amounts to proving that the conditions guaranteeing the LLC of DBPI hold. First, taking Sanger's algorithm for principal component analysis (pca), we show that it corresponds to iterating an LC map that can be written as the average of local maps held by agents with private data subsets. Applying DBPI then recovers a previous distributed pca algorithm, which lacked a convergence proof, thus closing that gap. In the second instantiation, we show that a variant of the expectation-maximization (EM) algorithm for parameter estimation from noisy, faulty measurements in sensor networks can be written as iterating an LC map that is the average of local maps. Consequently, the DBPI framework yields a distributed algorithm automatically inheriting the LLC guarantee of its centralized counterpart. Verifying the LC condition for EM is nontrivial (as the underlying operator depends on random samples) and a contribution in itself, possibly of independent interest. Finally, we illustrate experimentally the linear convergence of the proposed distributed EM algorithm, contrasting with the sub-linear rate of the previous version.
Robust subspace tracking is a real-time solution for suppressing harsh interference and estimating the target subspace in complex electromagnetic environments. In this article, a robust and decentralized subspace trac...
详细信息
Robust subspace tracking is a real-time solution for suppressing harsh interference and estimating the target subspace in complex electromagnetic environments. In this article, a robust and decentralized subspace tracking method is proposed. The multisensor array is divided into a number of nodes, each attached with a processor and no central processing unit (CPU) is deployed. In order to reduce the impact of a burst pulse, a robust real-time update algorithm of the subspace is designed through the weighted least squares method. The optimization model established in this article is robust to synchronization error. Then a subspace real-time update algorithm is proposed based on the average consensus (AC) method that integrates the information of distributed arrays. The computational complexity and convergence properties of the proposed algorithm are also investigated. Simulation results show that the proposed approach converges to the subspace estimation error by an order of magnitude compared with the single-node algorithm.
distributed pca aims to implement dimension reduction for data stored on multiple agents. The conventional distributed pca encounters the bottleneck of computation when the dimension of local data is large. In this wo...
详细信息
ISBN:
(纸本)9781728172019
distributed pca aims to implement dimension reduction for data stored on multiple agents. The conventional distributed pca encounters the bottleneck of computation when the dimension of local data is large. In this work, we propose a distributed pca algorithm with local processing based on randomized methods for the star network topology (master-slave networks) with distributed row observations. Local matrix approximation with randomized methods allows us to accelerate the computation with an acceptable loss of precision significantly. The results of numerical experiments show that the proposed algorithm can achieve satisfactory decomposition results with much lower computational complexity.
Principal Component Analysis (pca) and Singular Value Decomposition (SVD) are widely used in dimension reduction, feature extraction, low-rank matrix approximation and so on. In large-scale applications, a common alte...
详细信息
ISBN:
(纸本)9781538621622
Principal Component Analysis (pca) and Singular Value Decomposition (SVD) are widely used in dimension reduction, feature extraction, low-rank matrix approximation and so on. In large-scale applications, a common alternative is to use cluster which have multiple nodes and multiple cores to accelerate the time of solving problem. Most of the existing distributed pca algorithm focus on reducing the communication, and there is little attention to the frequent waiting phenomenon caused by the synchronization mechanism. Meanwhile, most of these works are based on either the distributed memory of the processes-level parallelism or the shared memory of threads-level parallelism. In this paper, we propose a fast distributed pca algorithm with variance reduced, which based on stochastic sampling and Stale Synchronous Parallel. Our algorithm contains the processes-level and threads-level parallelism. Experiments on the "Tianhe-2" super computer demonstrate that our algorithm has a good performance, speedup, and scalability.
Principal component analysis (pca) is not only a fundamental dimension reduction method, but is also a widely used network anomaly detection technique. Traditionally, pca is performed in a centralized manner, which ha...
详细信息
ISBN:
(纸本)9781467394574
Principal component analysis (pca) is not only a fundamental dimension reduction method, but is also a widely used network anomaly detection technique. Traditionally, pca is performed in a centralized manner, which has poor scalability for large distributed systems, on account of the large network bandwidth cost required to gather the distributed state at a fusion center. Consequently, several recent works have proposed various distributed pca algorithms aiming to reduce the communication overhead incurred by pca without losing its inferential power. This paper evaluates the tradeoff between communication cost and solution quality of two distributed pca algorithms on a real domain name system (DNS) query dataset from a large network. We also apply the distributed pca algorithm in the area of network anomaly detection and demonstrate that the detection accuracy of both distributed pca-based methods has little degradation in quality, yet achieves significant savings in communication bandwidth.
暂无评论