Yifan Wu, Kai Wang, Hongjin He, Solving basis pursuit revisited: When ADMM meets the inherent separable structure

Full Text: PDF
DOI: 10.23952/jano.7.2025.1.01
Volume 7, Issue 1, 1 April 2025, Pages 1-28

Abstract. The Basis Pursuit (BP) problem refers to the task of finding a minimum $\ell_1$ -norm solution to an underdetermined linear system, which is a fundamental problem in compressed sensing. It has been demonstrate that the BP problem can be efficiently solved by using some state-of-the-art first-order optimization algorithms based on the Augmented Lagrangian method, which can successfully circumvent the difficulty caused by the nondifferentiable objective. In this paper, we revisit the implementation of the Alternating Direction Method of Multipliers (ADMM) to solve the BP problem. Notably, by reformulating the BP problem as a naturally separable minimization problem, without relying on additional auxiliary variables, we can obtain two more efficient BP solvers, which can save storage space to speed up the process of solving the BP problem. Some numerical results demonstrate the reliability and efficiency of our approach. Furthermore, we conclude that ADMM would be more efficient when the inherent separable structure of the problem is effectively exploited.

How to Cite this Article:
Y. Wu, K. Wang, H. He, Solving basis pursuit revisited: When ADMM meets the inherent separable structure, J. Appl. Numer. Optim. 7 (2025), 1-28.