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.
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.
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