On the Complexity of the Weighted Fused Lasso

Abstract--The solution path of the 1D fused lasso for ann - dimensional input is piecewise linear with O (n) segments [1], [2]. However, existing proofs of this bound do not hold for the weighted fused lasso. We also give a new, very simple, proof of the O (n) bound for the fused lasso. There are efficient algorithms to solve 1FL for a fixedγ . This algorithm has recently been improved to a version, [8], that finishes inO (n) steps. Iterative algorithms, mostly first-order fixed-point methods, include [11]-[19]. Some of these are based on the ADMM method, known to achieve the fastest possible convergence rate among all first other methods, [20], [21]. However, in many applications, when precision is crucial, or when implementing a termination procedure has a non-negligible computational cost, direct algorithm are preferred.