Distributed basis pursuit

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

Research output: Contribution to journalArticle

Abstract

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
Volume60
Issue number4
DOIs
Publication statusPublished - Apr 2012

Keywords

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

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Signal Processing

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

  • Cite this

    Mota, J. F. C., Xavier, J. M. F., Aguiar, P. M. Q., & Püschel, M. (2012). Distributed basis pursuit. IEEE Transactions on Signal Processing, 60(4), 1942-1956. [6119236]. https://doi.org/10.1109/TSP.2011.2182347