We consider solving minimization problems with $\ell_1$-regularization: $$\min \|x\|_1 + \mu f(x),$$ particularly for $f(x) = \frac{1}{2}\|Ax-b\|_M^2$ where $A \in \R^{m \times n}$ with $m < n$. Our goal is to construct efficient and robust algorithms for solving large-scale problems with dense data, and our approach is based on two powerful algorithmic ideas, operator-splitting and continuation. Theoretical contributions of the paper include the establishment of $q$-linear rate of convergence for our algorithm applied to objectives with convex, but not necessarily strictly convex, $f$. We present numerical results on solving compressed sensing problems of various types, showing that on large-scale problems with noisy data the performance of our algorithm compares favorably with that of several state-of-the-art algorithms.
Citation
Rice CAAM Technical Report TR07-07