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