Alternating Direction Algorithms for ${\ell }_1$-Problems in Compressive Sensing

Abstract

In this paper, we propose and study the use of alternating direction algorithms for several ${\ell }_1$-norm minimization problems arising from sparse solution recovery in compressive sensing, including the basis pursuit problem, the basis-pursuit denoising problems of both unconstrained and constrained forms, as well as others. We present and investigate two classes of algorithms derived from either the primal or the dual forms of the ${\ell }_1$-problems. The construction of the algorithms consists of two main steps: (1) to reformulate an ${\ell }_1$-problem into one having partially separable objective functions by adding new variables and constraints; and (2) to apply an exact or inexact alternating direction method to the resulting problem. The derived alternating direction algorithms can be regarded as first-order primal-dual algorithms because both primal and dual variables are updated at each and every iteration. Convergence properties of these algorithms are established or restated when they already exist. Extensive numerical results in comparison with several state-of-the-art algorithms are given to demonstrate that the proposed algorithms are efficient, stable and robust. Moreover, we present numerical results to emphasize two practically important but perhaps overlooked points. One point is that algorithm speed should always be evaluated relative to appropriate solution accuracy; another is that whenever erroneous measurements possibly exist, the ${\ell }_1$-norm fidelity should be the fidelity of choice in compressive sensing.

References in corpus (3)

• Exact Matrix Completion via Convex Optimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• A Fast Algorithm for the Constrained Formulation of Compressive Image Reconstruction and Other Linear Inverse Problems

Cited by in corpus (41)

• A survey of sparse representation: algorithms and applications
• A non-adapted sparse approximation of PDEs with stochastic inputs
• Robust Low-rank Tensor Recovery: Models and Algorithms
• Constructing the L2-Graph for Robust Subspace Learning and Subspace Clustering
• A Survey of mmWave-based Human Sensing: Technology, Platform and Applications
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• Bregman Alternating Direction Method of Multipliers
• An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
• Can Image-Level Labels Replace Pixel-Level Labels for Image Parsing
• Jump-sparse and sparse recovery using Potts functionals
• Fast L1-Minimization Algorithms For Robust Face Recognition
• Scalable splitting algorithms for big-data interferometric imaging in the SKA era
• Recursive Recovery of Sparse Signal Sequences from Compressive Measurements: A Review
• Sparse Signal Recovery via Generalized Entropy Functions Minimization
• Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods
• Linearized Alternating Direction Method with Adaptive Penalty and Warm Starts for Fast Solving Transform Invariant Low-Rank Textures
• Compressed sensing with sparse corruptions: Fault-tolerant sparse collocation approximations
• Locating and quantifying gas emission sources using remotely obtained concentration data
• Self Equivalence of the Alternating Direction Method of Multipliers
• Minimization of fraction function penalty in compressed sensing
• The MUSIC Algorithm for Sparse Objects: A Compressed Sensing Analysis
• A Constrained Random Demodulator for Sub-Nyquist Sampling
• Distributed recovery of jointly sparse signals under communication constraints
• LADMM-Net: An Unrolled Deep Network For Spectral Image Fusion From Compressive Data
• Robust Image Analysis by L1-Norm Semi-supervised Learning
• Nonconvex Sorted ${\ell }_1$ Minimization for Sparse Approximation
• Parallel Direction Method of Multipliers
• A Fourier dimensionality reduction model for big data interferometric imaging
• Metrics for Evaluating the Efficiency of Compressing Sensing Techniques
• Nonmonotone Barzilai-Borwein Gradient Algorithm for ${\ell }_1$-Regularized Nonsmooth Minimization in Compressive Sensing
• Evolutionary Self-Expressive Models for Subspace Clustering
• Constructing test instances for Basis Pursuit Denoising
• Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems
• Scalar Quantization as Sparse Least Square Optimization
• Compressive Imaging of Subwavelength Structures II. Periodic Rough Surfaces
• An Extragradient-Based Alternating Direction Method for Convex Minimization
• Speeding up Linear Programming using Randomized Linear Algebra
• A Unified Approach for Minimizing Composite Norms
• Three-component Pomeron model in high energy pp- and pp- elastic scattering
• A First-order Augmented Lagrangian Method for Compressed Sensing
• A Homotopy Coordinate Descent Optimization Method for $l_0$-Norm Regularized Least Square Problem