A proximal-gradient homotopy method for the sparse least-squares problem (Q2848186)

The authors deal with the \(l_1\)-regularized least squares problem, proposing and analyzing an efficient numerical method for solving it. An approximate homotopy continuation method is used, solving the \(l_1\)-regularized least squares problem with a large parameter \(\lambda\) first and gradually decreasing \(\lambda\) until the targeted regularization is obtained. For each \(\lambda\), the problem is solved by a proximal gradient method up to the desired precision, getting a solution, which is the initial point in the next iteration corresponding to the next value \(\lambda\). The resulting technique is called proximal gradient homotopy method in this paper. The method has a provable low iteration complexity in specific algorithmic conditions. The overall iteration complexity and the overall computational cost are theoretically evaluated. Empirical results, which support the authors' theoretical analysis, are finally presented.