A linearized Bregman algorithm for decentralized basis pursuit

K. Yuan, Q. Ling, W. Yin, A. Ribeiro

Published in EUSIPCO’13

Overview

We solve a decentralized basis pursuit problem in a multiagent system, where each agent holds part of the linear observations on a common sparse vector, and all the agents collaborate to recover the sparse vector through limited neighbor-to-neighbor communication.

The proposed decentralized linearized Bregman algorithm solves the Lagrange dual of an augmented ell_1 model that is equivalent to basis pursuit. The fact that this dual problem is unconstrained and differentiable enables a lightweight yet ef´Čücient decentralized gradient algorithm.

We prove nearly linear convergence of the algorithm in the sense that uniformly for every agent i, the error obeys |x_i(k) - x^*|< e(k) and e(k) < rho e(k-1) + gamma, where rho <1 and gamma>0 are independent of k or i. Numerical experiments demonstrate this convergence.

Citation

K. Yuan, Q. Ling, W. Yin, A. Ribeiro, A linearized Bregman algorithm for decentralized basis pursuit, EUSIPCO, 2013.


« Back