Distributed Basis Pursuit
arXiv:1009.1128 · doi:10.1109/TSP.2011.2182347
Abstract
We propose a distributed algorithm for solving the optimization problem Basis Pursuit (BP). BP finds the least L1-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.
Preprint of the journal version of the paper; IEEE Transactions on Signal Processing, Vol. 60, Issue 4, April, 2012
References in corpus (1)
Cited by in corpus (43)
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
- D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
- A linear algorithm for optimization over directed graphs with geometric convergence
- Sparse Distributed Learning Based on Diffusion Adaptation
- A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
- Distributed Optimization With Local Domains: Applications in MPC and Network Flows
- A Sparsity-Aware Adaptive Algorithm for Distributed Learning
- Dictionary Learning over Distributed Models
- Distributed Compressed Sensing For Static and Time-Varying Networks
- Diffusion LMS for Multitask Problems with Local Linear Equality Constraints
- Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
- Supervised Learning Under Distributed Features
- On the Convergence of Decentralized Gradient Descent
- Diffusion Adaptation Strategies for Distributed Estimation over Gaussian Markov Random Fields
- Norm-1 Regularized Consensus-based ADMM for Imaging with a Compressive Antenna
- Application of Compressive Sensing Techniques in Distributed Sensor Networks: A Survey
- Greedy Sparsity-Promoting Algorithms for Distributed Learning
- Decentralized and Collaborative Subspace Pursuit: A Communication-Efficient Algorithm for Joint Sparsity Pattern Recovery with Sensor Networks
- FADE: Fast and Asymptotically efficient Distributed Estimator for dynamic networks
- A Unified Algorithmic Framework for Distributed Adaptive Signal and Feature Fusion Problems -- Part I: Algorithm Derivation
- Alternating Directions Dual Decomposition
- Multi-Processor Approximate Message Passing Using Lossy Compression
- Statistical Physics and Information Theory Perspectives on Linear Inverse Problems
- Performance Trade-Offs in Multi-Processor Approximate Message Passing
- Communication-Efficient Algorithms For Distributed Optimization
- Distributed Approximate Message Passing for Compressed Sensing
- NPGA: A Unified Algorithmic Framework for Decentralized Constraint-Coupled Optimization
- DCOOL-NET: Distributed cooperative localization for sensor networks
- Optimal Trade-offs in Multi-Processor Approximate Message Passing
- Analysis of Democratic Voting Principles used in Distributed Greedy Algorithms
- An Overview of Multi-Processor Approximate Message Passing
- Distributed Error-Identification and Correction using Block-Sparse Optimization
- A general framework for decentralized optimization with first-order methods
- Distributed soft thresholding for sparse signal recovery
- Deterministic and Randomized Diffusion based Iterative Generalized Hard Thresholding (DiFIGHT) for Distributed Sparse Signal Recovery
- Dynamic Average Diffusion with randomized Coordinate Updates
- Distributed L1-state-and-fault estimation for Multi-agent systems
- Column Partition based Distributed Algorithms for Coupled Convex Sparse Optimization: Dual and Exact Regularization Approaches
- Bias estimation in sensor networks
- Design and Analysis of a Greedy Pursuit for Distributed Compressed Sensing
- Decentralized Subspace Pursuit for Joint Sparsity Pattern Recovery
- Cross-layer estimation and control for Cognitive Radio: Exploiting Sparse Network Dynamics