The Homotopy Method Revisited: Computing Solution Paths of\n $\\ell_1$-Regularized Problems

Björn Bringmann, Daniel Cremers, Felix Krahmer, Michael Møller

Abstract

$\ell_1$-regularized linear inverse problems are frequently used in signal processing, image analysis, and statistics. The correct choice of the regularization parameter $t \in \mathbb{R}_{\geq 0}$ is a delicate issue. Instead of solving the variational problem for a fixed parameter, the idea of the homotopy method is to compute a complete solution path $u(t)$ as a function of $t$. In a celebrated paper by Osborne, Presnell, and Turlach, it has been shown that the computational cost of this approach is often comparable to the cost of solving the corresponding least squares problem. Their analysis relies on the one-at-a-time condition, which requires that different indices enter or leave the support of the solution at distinct regularization parameters. In this paper, we introduce a generalized homotopy algorithm based on a nonnegative least squares problem, which does not require such a condition, and prove its termination after finitely many steps. At every point of the path, we give a full characterization of all possible directions. To illustrate our results, we discuss examples in which the standard homotopy method either fails or becomes infeasible. To the best of our knowledge, our algorithm is the first to provably compute a full solution path for an arbitrary combination of an input matrix and a data vector.

Introduction: The Challenge of the Regularization Path

In signal processing and statistics, recovering a sparse signal $u$ from noisy linear measurements $f = Au + \eta$ is a fundamental task. The standard approach is $\ell_1$-regularization, often called the Lasso, which minimizes the following objective: $$\min_u \frac{1}{2} \|Au - f\|_2^2 + t \|u\|_1$$ The performance of this model depends critically on the regularization parameter $t$. A large $t$ leads to overly sparse, smoothed results, while a small $t$ fails to filter out noise.

A typical solution path $u(t)$ where components enter and leave the support as the regularization parameter $t$ varies.

Homotopy methods aim to compute the solution $u(t)$ for all $t \in [0, \infty)$ simultaneously. Since the solution path is piecewise linear, the algorithm only needs to identify the "kinks"—the specific values of $t$ where the set of active variables (the support) changes. However, classic algorithms like LARS rely on a "one-at-a-time" condition, assuming only one variable enters or leaves the support at any given $t$. In practice, especially with structured data, this condition is often violated, causing standard software to crash or fail to find the correct path.

The Generalized Homotopy Method

This paper introduces a Generalized Homotopy Method that removes the "one-at-a-time" restriction, providing a robust framework for any input.

Direction as Optimization

Instead of solving a simple linear system to find the next path direction—a method that fails when multiple indices change simultaneously—the authors characterize the set of all valid directions as the solution to a non-negative least squares (NNLS) problem. This formulation treats the "kinks" not as simple transition points, but as local optimization problems that determine the next optimal trajectory for the entire vector.

The Minimal $\ell_2$ Norm Rule

Among the potentially multiple valid directions that maintain optimality, the algorithm specifically selects the one with the minimum $\ell_2$ norm. The authors provide a rigorous proof that this specific selection rule ensures the algorithm reaches $t=0$ in a finite number of steps, even in highly degenerate cases where the solution might not be unique.

Key Insights and Results

A major contribution of this work is debunking the "one-at-a-time" myth. While often assumed to be rare, degenerate cases where multiple variables change at once are common in applications involving random sign matrices or exact measurements.

A complex solution path exhibiting oscillatory behavior. The zoom-in (right) shows $u_2$ and $u_3$ undergoing multiple changes in direction, a scenario that can cause standard homotopy methods to fail.

The proposed NNLS framework provides a unified way to handle variables hitting the "equicorrelation" boundary and variables leaving the support simultaneously. The authors demonstrate that even when the solution $u(t)$ is unique, algorithms can become unstable if they don't correctly account for the geometry of the $\ell_1$ ball. Their method correctly identifies paths in cases where standard implementations might pick directions with incorrect signs.

Conclusion

This algorithm is the first to provably compute a full solution path for any arbitrary combination of input matrix $A$ and data $f$. While solving an NNLS problem at every kink introduces some computational overhead compared to standard linear solvers, it ensures robustness and finite termination. Future work may extend this framework to other polyhedral regularizations, such as Total Variation (TV) or $\ell_\infty$ norms, and non-quadratic data fidelity terms.

Summary updated

Abstract

$ \\ell_1 $-regularized linear inverse problems are frequently used in signal\nprocessing, image analysis, and statistics. The correct choice of the\nregularization parameter $ t \\in \\mathbb{R}_{\\geq 0} $ is a delicate issue.\nInstead of solving the variational problem for a fixed parameter, the idea of\nthe homotopy method is to compute a complete solution path $ u(t) $ as a\nfunction of $ t $. In a celebrated paper by Osborne, Presnell, and Turlach, it\nhas been shown that the computational cost of this approach is often comparable\nto the cost of solving the corresponding least squares problem. Their analysis\nrelies on the one-at-a-time condition, which requires that different indices\nenter or leave the support of the solution at distinct regularization\nparameters. In this paper, we introduce a generalized homotopy algorithm based\non a nonnegative least squares problem, which does not require such a\ncondition, and prove its termination after finitely many steps. At every point\nof the path, we give a full characterization of all possible directions. To\nillustrate our results, we discuss examples in which the standard homotopy\nmethod either fails or becomes infeasible. To the best of our knowledge, our\nalgorithm is the first to provably compute a full solution path for an\narbitrary combination of an input matrix and a data vector.\n
BibTeX
@article{bringmann2018homotopy,
  author = {Björn Bringmann and Daniel Cremers and Felix Krahmer and Michael Møller},
  title = {{The Homotopy Method Revisited: Computing Solution Paths of\textbackslash\{\}n $\textbackslash\{\}\textbackslash\{\}ell\_1$-Regularized Problems}},
  journal = {Math. Comput.},
  year = {2018},
  doi = {10.1090/mcom/3287},
}
Figure