Alternating Direction Algorithms for 1-Problems in Compressive Sensing

By Junfeng Yang, Yin Zhang. SIAM Journal on Scientific Computing, 2009

1,290 citations recorded by the source corpus.

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, and others. We present and investigate two classes of algorithms derived from either the primal or the dual form of $\ell_1$-problems. The construction of the algorithms consists of two main steps: (1) to reformulate an $\ell_1$-problem into one having blockwise separable objective functions by adding new variables and constraints; and (2) to apply an exact or inexact alternating direction method to the augmented Lagrangian function of 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 every iteration. Convergence properties of these algorithms are established or restated when they already exist. Extensive numerical experiments are performed, using randomized partial Walsh-Hadamard sensing matrices, to demonstrate the versatility and effectiveness of the proposed approach. Moreover, we present numerical results to emphasize two practically important but perhaps overlooked points: (i) that algorithm speed should be evaluated relative to appropriate solution accuracy; and (ii) that when erroneous measurements possibly exist, the $\ell_1$-fidelity should generally be preferable to the $\ell_2$-fidelity.

Subfields: Biomedical Engineering, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/773ba83d5520cbc579f84bba8c24849f90705dd1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

Citations in the corpus

Stochastic Alternating Direction Method of Multipliers (2013, methodology): “On the practical side, ADMM has been applied to a wide range of application domains, such as compressed sensing (Yang & Zhang, 2011), image restoration (Goldstein & Osher, 2009), video processing and matrix completion (Goldfarb et al., 2010).”
Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers (2011, neutral): “[173] compares and benchmarks a number of representative algorithms, including gradient projection [73, 102], homotopy methods [52], iterative shrinkage-thresholding [45], proximal gradient [132, 133, 11, 12], augmented Lagrangian methods [175], and interior-point methods [103].”
Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation (2011, background): “In previous ADM and LADM approaches [15, 21, 20], the penalty parameter β is fixed.”
Parallel Multi-Block ADMM with o(1 / k) Convergence (2013, neutral): “We also include the YALL1 package [37] in the experiment, which is one of the stateof-the-art solvers for 1 minimization.”
A non-adapted sparse approximation of PDEs with stochastic inputs (2010, background): “For comprehensive discussions on this subject, the interested reader is referred to [14, 62, 37, 4, 69, 61].”
Robust sparse coding for face recognition (2011, positive): “(2) because both of them can have the following Lagrangian formulation: min α {∥y −Dα∥1 + λ ∥α∥1}[26].”
Global Convergence of Splitting Methods for Nonconvex Composite Optimization (2014, methodology): “This has been widely used recently; see, for example [8, 9, 27, 28, 30].”
Accelerated dynamic MRI exploiting sparsity and low-rank structure: k-t SLR (2011, positive): “Similar alternating directions methods are widely used in compressed sensing and TV minimization [25], [34].”
Convex Optimization in Normed Spaces (2015, methodology): “See also [104] ⊓⊔ A variant of the forward-backward algorithm was proposed by Tseng [101] for min{ f1(x) + f2(x) : x ∈ C}.”
Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems (2013, background): “a large number of recent applications in diverse areas such as compressed sensing [2], regularized estimation [3], image processing [4], machine learning [5], and resource allocation in wireless networks [6].”
Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding (2013, methodology): “These techniques have been used in a broad range of applications including imaging [20, 41, 61], control [3, 49, 57, 62], estimation [82], signal processing [22, 23, 25, 86], finance [9], distributed optimization [47, 65], and many others.”