A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem

By Lin Xiao, Tong Zhang. 2012

154 citations recorded by the source corpus.

We consider solving the $\ell_1$-regularized least-squares ($\ell_1$-LS) problem in the context of sparse recovery for applications such as compressed sensing. The standard proximal gradient method, also known as iterative soft-thresholding when applied to this problem, has low computational cost per iteration but a rather slow convergence rate. Nevertheless, when the solution is sparse, it often exhibits fast linear convergence in the final stage. We exploit the local linear convergence using a homotopy continuation strategy, i.e., we solve the $\ell_1$-LS problem for a sequence of decreasing values of the regularization parameter, and use an approximate solution at the end of each stage to warm start the next stage. Although similar strategies have been studied in the literature, there have been no theoretical analysis of their global iteration complexity. This paper shows that under suitable assumptions for sparse recovery, the proposed homotopy strategy ensures that all iterates along the homotopy sol...

Subfields: Biomedical Engineering, Computational Mechanics, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, background): “Xiao and Zhang (2013) also assume the RIP property and show linear convergence using a homotopy method that slowly decreases the value of λ. Agarwal et al. (2012) give a linear convergence rate under a modified restricted strong convexity and modified restricted smoothness assumption.”
Optimal Black-Box Reductions Between Optimization Objectives (2016, methodology): “However, to the best of our knowledge, all existing homotopy analysis either only work for specific algorithms [6, 25, 31] or solve only special problems [33].”
A unified approach to error bounds for structured convex optimization problems (2015, methodology): “It has been observed numerically that ﬁrst-order methods for solving structured instances of Problem (1) converge at a much faster rate than that suggested by the theory; see, e.g. , [11, 42].”