Fixed-Point Continuation for ₁-Minimization: Methodology and Convergence

We present a framework for solving the large-scale ₁-regularized convex minimization problem: \ \|x\|₁+ 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 ; continuation refers to approximately following the path traced by the optimal value of x as 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 our convergence results, is demonstrated to facilitate the construction of practical algorithms.