A Dynamic Programming Algorithm for the Fused Lasso and L0-Segmentation

By Nicholas Alexander Johnson. 2013

121 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Control and Systems Engineering, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Thomas Pock
2. Antonin Chambolle
3. Ali Shojaie
4. Noah R. Simon
5. Asad Haris
6. Matthew F. Dixon

In Control and Systems Engineering

1. Antonin Chambolle
2. Thomas Pock
3. Ali Shojaie
4. Noah R. Simon

In Statistics and Probability

1. Thomas Pock
2. Ali Shojaie
3. Asad Haris
4. Antonin Chambolle
5. Noah R. Simon
6. Matthew F. Dixon

Citations in the corpus

• Generalized Sparse Additive Models (2019, background): “…are already efficient solvers for solving (13): with the k -th order total variation penalty, (13) can be solved exactly in 2 n operations for k = 0 [Johnson, 2013], or iteratively in roughly O (( k + 1) n ) operations for k ≥ 1 [Ramdas and Tibshirani, 2015]; with the convex indicator of an M…”
• Penalized classification using Fisher’s linear discriminant (2011, unknown): “• If ˜ Σ w is a diagonal estimate for Σ w then (22) is a diagonal fused lasso problem, for which fast algorithms have been proposed (see e.g. Hoefling, 2009; Johnson, 2010).”
• An introduction to continuous optimization for imaging (2016, background): “312 A. Chambolle and T. Pock N. A. Johnson (2013), ‘A dynamic programming algorithm for the fused Lasso and l0-segmentation’, J. Comput.”
• Fast and Flexible ADMM Algorithms for Trend Filtering (2014, unknown): “Two exact, linear time 1d fused lasso solvers were given by Davies & Kovac (2001), Johnson (2013). The former is based on taut strings, and the latter on dynamic programming.”