CAPPA: Continuous-time Accelerated Proximal Point Algorithm for Sparse Recovery

Abstract

This paper develops a novel Continuous-time Accelerated Proximal Point Algorithm (CAPPA) for ${\ell }_1$-minimization problems with provable fixed-time convergence guarantees. The problem of ${\ell }_1$-minimization appears in several contexts, such as sparse recovery (SR) in Compressed Sensing (CS) theory, and sparse linear and logistic regressions in machine learning to name a few. Most existing algorithms for solving ${\ell }_1$-minimization problems are discrete-time, inefficient and require exhaustive computer-guided iterations. CAPPA alleviates this problem on two fronts: (a) it encompasses a continuous-time algorithm that can be implemented using analog circuits; (b) it betters LCA and finite-time LCA (recently developed continuous-time dynamical systems for solving SR problems) by exhibiting provable fixed-time convergence to optimal solution. Consequently, CAPPA is better suited for fast and efficient handling of SR problems. Simulation studies are presented that corroborate computational advantages of CAPPA.

arXiv comment6 pages, 5 figures

References in corpus (5)

• NESTA: A Fast and Accurate First-order Method for Sparse Recovery
• A Variational Perspective on Accelerated Methods in Optimization
• Learning optimal nonlinearities for iterative thresholding algorithms
• Convergence Speed of a Dynamical System for Sparse Recovery
• Discrete and Continuous-time Soft-Thresholding with Dynamic Inputs