7 Dec 2009 | JUNFENG YANG* AND YIN ZHANG \(\dagger\)
This paper proposes and studies alternating direction algorithms for solving $\ell_1$-norm minimization problems in compressive sensing, including basis pursuit, basis pursuit denoising (both constrained and unconstrained), and other related problems. The algorithms are derived from either the primal or dual forms of the $\ell_1$-problems and involve reformulating the $\ell_1$-problem into one with partially separable objective functions, followed by applying an exact or inexact alternating direction method. These algorithms are first-order primal-dual algorithms, updating both primal and dual variables at each iteration. The convergence properties of these algorithms are established or restated when they already exist. Numerical results show that the proposed algorithms are efficient, stable, and robust. The paper also emphasizes two practically important points: algorithm speed should be evaluated relative to appropriate solution accuracy, and $\ell_1$-norm fidelity should be used in compressive sensing when erroneous measurements may exist. The paper presents extensive numerical results comparing the proposed algorithms with several state-of-the-art algorithms, demonstrating their performance in various scenarios. The algorithms are applied to solve $\ell_1$-minimization problems, including the basis pursuit problem, basis pursuit denoising, and the $\ell_1/\ell_1$ model. The paper also discusses the application of these algorithms to real and nonnegative signals, and provides a detailed analysis of the convergence properties and numerical performance of the algorithms. The results show that the $\ell_1/\ell_1$ model is preferred when there is a possibility of erroneous measurements, while the $\ell_2$-norm fidelity is preferred when there is no impulsive noise. The paper concludes that the proposed algorithms are effective and robust for solving $\ell_1$-minimization problems in compressive sensing.This paper proposes and studies alternating direction algorithms for solving $\ell_1$-norm minimization problems in compressive sensing, including basis pursuit, basis pursuit denoising (both constrained and unconstrained), and other related problems. The algorithms are derived from either the primal or dual forms of the $\ell_1$-problems and involve reformulating the $\ell_1$-problem into one with partially separable objective functions, followed by applying an exact or inexact alternating direction method. These algorithms are first-order primal-dual algorithms, updating both primal and dual variables at each iteration. The convergence properties of these algorithms are established or restated when they already exist. Numerical results show that the proposed algorithms are efficient, stable, and robust. The paper also emphasizes two practically important points: algorithm speed should be evaluated relative to appropriate solution accuracy, and $\ell_1$-norm fidelity should be used in compressive sensing when erroneous measurements may exist. The paper presents extensive numerical results comparing the proposed algorithms with several state-of-the-art algorithms, demonstrating their performance in various scenarios. The algorithms are applied to solve $\ell_1$-minimization problems, including the basis pursuit problem, basis pursuit denoising, and the $\ell_1/\ell_1$ model. The paper also discusses the application of these algorithms to real and nonnegative signals, and provides a detailed analysis of the convergence properties and numerical performance of the algorithms. The results show that the $\ell_1/\ell_1$ model is preferred when there is a possibility of erroneous measurements, while the $\ell_2$-norm fidelity is preferred when there is no impulsive noise. The paper concludes that the proposed algorithms are effective and robust for solving $\ell_1$-minimization problems in compressive sensing.