Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence

We present a framework for solving the large-scale $\ell_1$-regularized convex minimization problem:\[ \min\|x\|_1+\mu f(x). \] Our approach is based on two powerful algorithmic ideas: operator-splitting and continuation. Operator-splitting results in a fixed-point algorithm for any given scalar $\mu$; continuation refers to approximately following the path traced by the optimal value of x as $\mu$ increases. In this paper, we study the structure of optimal solution sets, prove finite convergence for important quantities, and establish q-linear convergence rates for the fixed-point algorithm applied to problems with $f(x)$ convex, but not necessarily strictly convex. The continuation framework, motivated by…