ALTERNATING DIRECTION ALGORITHMS FOR \(\ell_1\)-PROBLEMS IN COMPRESSIVE SENSING

ALTERNATING DIRECTION ALGORITHMS FOR \(\ell_1\)-PROBLEMS IN COMPRESSIVE SENSING

7 Dec 2009 | JUNFENG YANG* AND YIN ZHANG \(\dagger\)
This paper proposes and studies the use of alternating direction (ADM) algorithms for solving several $\ell_1$-norm minimization problems in compressive sensing, including basis pursuit, basis pursuit denoising (BPDN), and their constrained forms. The algorithms are derived from either the primal or dual forms of the $\ell_1$-problems, involving two main steps: reformulating the problem with partially separable objective functions and applying an exact or inexact alternating direction method. The proposed algorithms are first-order primal-dual methods that update both primal and dual variables at each iteration. Convergence properties of these algorithms are established or restated. Extensive numerical results compare the proposed algorithms with several state-of-the-art methods, demonstrating their efficiency, stability, and robustness. The paper also highlights two practical points: evaluating algorithm speed relative to solution accuracy and the importance of using $\ell_1$-norm fidelity when erroneous measurements are present.This paper proposes and studies the use of alternating direction (ADM) algorithms for solving several $\ell_1$-norm minimization problems in compressive sensing, including basis pursuit, basis pursuit denoising (BPDN), and their constrained forms. The algorithms are derived from either the primal or dual forms of the $\ell_1$-problems, involving two main steps: reformulating the problem with partially separable objective functions and applying an exact or inexact alternating direction method. The proposed algorithms are first-order primal-dual methods that update both primal and dual variables at each iteration. Convergence properties of these algorithms are established or restated. Extensive numerical results compare the proposed algorithms with several state-of-the-art methods, demonstrating their efficiency, stability, and robustness. The paper also highlights two practical points: evaluating algorithm speed relative to solution accuracy and the importance of using $\ell_1$-norm fidelity when erroneous measurements are present.
Reach us at info@study.space