FIXED-POINT CONTINUATION FOR l1-MINIMIZATION: METHODOLOGY AND CONVERGENCE

We present a framework for solving the large-scale l(1)-regularized convex minimization problem: min parallel to x parallel to(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 our convergence results, is demonstrated to facilitate the construction of practical algorithms.