A Homotopy Recursive-in-Model-Order Algorithm for Weighted Lasso

Abstract: We have designed a fast algorithm to solve weighted l1-minimization problems with NxN square “measuring” matrices. The method is recursive-in-model-order and tracks a homotopy path that goes through solutions of the optimization sub-tasks in the order of 1 through N. It thus yields solutions for all model orders and performs this task faster than the other methods. The algorithm might be viewed as an analogy to the famous Levinson-Durbin recursive algorithm, designed to solve the purely quadratic optimization program where the measuring matrix is a square symmetric Toeplitz matrix.

Matlab code: here


Z. Koldovský and P. Tichavský, “A Homotopy Recursive-in-Model-Order Algorithm for Weighted Lasso,” accepted for publication in Proc. of ICASSP 2014, Florence, Italy, May 2014. (here)