Skip to Main content Skip to Navigation
Conference papers

Distributed algorithms for basis pursuit

Abstract : The Basis Pursuit (BP) problem consists in finding a least `1 norm solution of the underdetermined linear system Ax = b. It arises in many areas of electrical engineering and applied mathematics. Applications include signal compression and modeling, estimation, fitting, and compressed sensing. In this paper, we explore methods for solving the BP in a distributed environment, i.e., when the computational resources and the matrix A are distributed over several interconnected nodes. Special instances of this distributed framework include sensor networks and distributed memory and/or processor platforms. We consider two distribution paradigms: either the columns or the rows of A are distributed across the nodes. The several algorithms that we present impose distinct requirements on the degree of connectivity of the network and the per-node computational complexity.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Thursday, March 19, 2009 - 4:58:51 PM
Last modification on : Saturday, June 2, 2018 - 11:24:01 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 11:40:39 PM


Files produced by the author(s)


  • HAL Id : inria-00369431, version 1



João F. C. Mota, João M. F. Xavier, Pedro M. Q. Aguiar, Markus Püschel. Distributed algorithms for basis pursuit. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Inria Rennes - Bretagne Atlantique, Apr 2009, Saint Malo, France. ⟨inria-00369431⟩



Record views


Files downloads