Details

Autor(en) / Beteiligte

• Andrade, Francisco
• Figueiredo, Mario A. T.
• Xavier, Jo ao

Titel

Distributed Banach-Picard Iteration: Application to Distributed Parameter Estimation and PCA

Ist Teil von

• IEEE transactions on signal processing, 2023-01, Vol.71, p.1-14

Ort / Verlag

New York: IEEE

Erscheinungsjahr

2023

Quelle

IEEE/IET Electronic Library (IEL)

Beschreibungen/Notizen

• In recent work, we proposed an algorithmic framework, distributed Banach-Picard iteration (DBPI), that allows a set of agents, linked by a communication network, to find a fixed point of a map with the following two properties: (a) it is the average of individual maps held by said agents; (b) it is locally contractive (LC). Given a map with those two properties, DBPI yields a distributed algorithm that provably inherits the local linear convergence (LLC) of the standard Banach-Picard iteration applied to the centralized (average) map. In this work, we show how DBPI is instantiated in two classical problems, a task that boils down to the (non-trivial) tasks of proving that the necessary conditions that guarantee the LLC of DBPI are satisfied. In the first instantiation, we take Sanger's algorithm for principal component analysis (PCA) and show that it corresponds to iterating an LC map that can be written as the average of local maps held by agents that have (private) subsets of the data. Applying DBPI to this problem recovers a previous distributed PCA algorithm, which lacked a convergence proof, a gap that our approach seamlessly closes. In the second instantiation, we show that a variant of the expectation-maximization (EM) algorithm for parameter estimation from noisy and faulty measurements in a sensor network can be written as the iteration of an LC map that is the average of local maps, each available at each node. Consequently, the DBPI framework yields a distributed version of this algorithm, which automatically inherits the LLC guarantee of its centralized counterpart. The verification of the LC condition for EM is technically challenging (as the underlying operator depends on random samples) and is a contribution in itself, which may be of independent interest. Finally, we illustrate experimentally the linear convergence of the proposed distributed EM algorithm, in contrast with the sub-linear rate of the previous version.