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.