Distributed Banach-Picard Iteration: Application to Distributed Parameter Estimation and PCA
Andrade, F. L.
;
Figueiredo, M. A. T.
; Xavier, J.
IEEE Transactions on Signal Processing Vol. 71, Nº 1, pp. 17 - 30, January, 2023.
ISSN (print): 1053-587X
ISSN (online): 1941-0476
Scimago Journal Ranking: 2,52 (in 2023)
Digital Object Identifier: 10.1109/TSP.2023.3239806
Download Full text PDF ( 992 KBs)
Downloaded 1 time
Abstract
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.