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

摘要: $ \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 solving variational problem for fixed parameter, idea homotopy method to compute complete solution path u(t) as function $. In celebrated paper by Osborne, Presnell, Turlach, it has been shown that computational cost this approach often comparable corresponding least squares problem. Their analysis relies on one-at-a-time condition, which requires different indices enter or leave support at distinct parameters. paper, we introduce generalized algorithm based nonnegative problem, does not require such prove its termination after finitely many steps. At every point path, give full characterization all possible directions. To illustrate our results, discuss examples standard either fails becomes infeasible. best knowledge, first provably an arbitrary combination input matrix data vector.