On the Complexity of the Weighted Fused Lasso
arXiv:1801.04987 · doi:10.1109/LSP.2018.2867800
Abstract
The solution path of the 1D fused lasso for an -dimensional input is piecewise linear with segments (Hoefling et al. 2010 and Tibshirani et al 2011). However, existing proofs of this bound do not hold for the weighted fused lasso. At the same time, results for the generalized lasso, of which the weighted fused lasso is a special case, allow segments (Mairal et al. 2012). In this paper, we prove that the number of segments in the solution path of the weighted fused lasso is , and that, for some instances, it is . We also give a new, very simple, proof of the bound for the fused lasso.
References in corpus (7)
- Pathwise coordinate optimization
- Fast and Flexible ADMM Algorithms for Trend Filtering
- Geometric properties of solutions to the total variation denoising problem
- Extensions of smoothing via taut strings
- On the performance of algorithms for the minimization of -penalized functionals
- How is Distributed ADMM Affected by Network Topology?
- An Explicit Rate Bound for the Over-Relaxed ADMM