The DFS fused Lasso: linear-time denoising over general graphs

MaRDI QIDQ4558501zbMATH OpenFDO

Authors Oscar-Hernan Madrid-Padilla, James Sharpnack, James G. Scott, Ryan J. Tibshirani

Publication date 22 November 2018

Full work available at URL https://arxiv.org/abs/1608.03384, http://jmlr.csail.mit.edu/papers/v18/16-532.html

zbMATH Keywords

depth-first searchfused Lassograph denoisingtotal variation denoising

Mathematics Subject Classification ID

Applications of graph theory (05C90) Probabilistic graphical models (62H22) Ridge regression; shrinkage estimators (Lasso) (62J07)

Abstract: The fused lasso, also known as (anisotropic) total variation denoising, is widely used for piecewise constant signal estimation with respect to a given undirected graph. The fused lasso estimate is highly nontrivial to compute when the underlying graph is large and has an arbitrary structure. But for a special graph structure, namely, the chain graph, the fused lasso---or simply, 1d fused lasso---can be computed in linear time. In this paper, we establish a surprising connection between the total variation of a generic signal defined over an arbitrary graph, and the total variation of this signal over a chain graph induced by running depth-first search (DFS) over the nodes of the graph. Specifically, we prove that for any signal, its total variation over the induced chain graph is no more than twice its total variation over the original graph. This connection leads to several interesting theoretical and computational conclusions. Denoting by $m$ and $n$ the number of edges and nodes, respectively, of the graph in question, our result implies that for an underlying signal with total variation $t$ over the graph, the fused lasso achieves a mean squared error rate of smash{$t^{2/3}{n}^{-2/3}$}. Moreover, precisely the same mean squared error rate is achieved by running the 1d fused lasso on the induced chain graph from running DFS. Importantly, the latter estimator is simple and computationally cheap, requiring only $O(m)$ operations for constructing the DFS-induced chain and $O(n)$ operations for computing the 1d fused lasso solution over this chain. Further, for trees that have bounded max degree, the error rate of smash{$t^{2/3}{n}^{-2/3}$} cannot be improved, in the sense that it is the minimax rate for signals that have total variation $t$ over the tree.

Recommendations

• On the total variation regularized estimator over a class of tree graphs
• Adaptive nonparametric regression with the \(K\)-nearest neighbour fused Lasso
• Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
• Properties and refinements of the fused Lasso
• Sharp MSE bounds for proximal denoising

Cites work

• A first-order primal-dual algorithm for convex problems with applications to imaging
• Adaptive piecewise polynomial estimation via trend filtering
• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Cut pursuit: fast algorithms to learn piecewise constant functions on general weighted graphs
• Diffusion wavelets
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1064667 (Why is no real title available?)
• Introduction to algorithms
• Introduction to nonparametric estimation
• Kernels and regularization on graphs.
• Learning Theory
• Local extremes, runs, strings and multiresolution. (With discussion)
• Locally adaptive regression splines
• Lower-Stretch Spanning Trees
• Minimax estimation via wavelet shrinkage
• Minimax Rates of Estimation for High-Dimensional Linear Regression Over \ell_q-Balls
• Multiple Change-Point Estimation With a Total Variation Penalty
• Nonlinear total variation based noise removal algorithms
• On stepwise pattern recovery of the fused Lasso
• On the approximation of curves by line segments using dynamic programming
• On the prediction performance of the Lasso
• On total variation minimization and surface evolution using parametric maximum flows
• Properties and refinements of the fused Lasso
• Random spanning trees and the prediction of weighted graphs
• Some remarks on distributed depth-first search.
• Sparsity and Smoothness Via the Fused Lasso
• The solution path of the generalized lasso
• Total variation on a tree
• Trend filtering on graphs
• Using petal-decompositions to build a low stretch spanning tree
• Wavelets on graphs via spectral graph theory

Cited in

(17)

• Sparse spatially clustered coefficient model via adaptive regularization
• Graph signal denoising using \(t\)-shrinkage priors
• Horseshoe shrinkage methods for Bayesian fusion estimation
• Sparse and smooth signal estimation: convexification of \(\ell_0\)-formulations
• Block-Wise Variable Selection for Clustering Via Latent States of Mixture Models
• Logistic regression with total variation regularization
• Adaptive rates for total variation image denoising
• Graphon estimation via nearest‐neighbour algorithm and two‐dimensional fused‐lasso denoising
• Quantile regression by dyadic CART
• Locally adaptive sparse additive quantile regression model with TV penalty
• Multivariate trend filtering for lattice data
• Transfer learning for piecewise-constant mean estimation: optimality, _1 and _0 penalization
• Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty
• Rank-one convexification for sparse regression
• Denoising over networks with applications to partially observed epidemics
• Asymptotic distribution of constrained nearly-isotonic graph fused Lasso
• Data-driven thresholding in denoising with spectral graph wavelet transform

Describes a project that uses

Uses Software

• condat_tv

This page was built for publication: The DFS fused Lasso: linear-time denoising over general graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558501)