Distributed basis pursuit

João F. C. Mota*, João M. F. Xavier, Pedro M. Q. Aguiar, Markus Püschel

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

159 Citations (Scopus)


We propose a distributed algorithm for solving the optimization problem Basis Pursuit (BP). BP finds the least ℓ 1-norm solution of the underdetermined linear system Ax = b and is used, for example, in compressed sensing for reconstruction. Our algorithm solves BP on a distributed platform such as a sensor network, and is designed to minimize the communication between nodes. The algorithm only requires the network to be connected, has no notion of a central processing node, and no node has access to the entire matrix A at any time. We consider two scenarios in which either the columns or the rows of A are distributed among the compute nodes. Our algorithm, named D-ADMM, is a decentralized implementation of the alternating direction method of multipliers. We show through numerical simulation that our algorithm requires considerably less communications between the nodes than the state-of-the-art algorithms.

Original languageEnglish
Article number6119236
Pages (from-to)1942-1956
Number of pages15
JournalIEEE Transactions on Signal Processing
Issue number4
Publication statusPublished - Apr 2012


  • Augmented Lagrangian
  • basis pursuit (BP)
  • distributed optimization
  • sensor networks

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Signal Processing


Dive into the research topics of 'Distributed basis pursuit'. Together they form a unique fingerprint.

Cite this