Trend Filtering on Graphs
This work provides a method for adaptive estimation on graphs, which is incremental as it generalizes an existing univariate technique to graph structures.
The authors tackled the problem of nonparametric regression on graphs by introducing graph trend filtering, which penalizes the ℓ₁ norm of discrete graph differences to achieve local adaptivity unmatched by ℓ₂-based smoothers, and they demonstrated its merits through examples and theory.
We introduce a family of adaptive estimators on graphs, based on penalizing the $\ell_1$ norm of discrete graph differences. This generalizes the idea of trend filtering [Kim et al. (2009), Tibshirani (2014)], used for univariate nonparametric regression, to graphs. Analogous to the univariate case, graph trend filtering exhibits a level of local adaptivity unmatched by the usual $\ell_2$-based graph smoothers. It is also defined by a convex minimization problem that is readily solved (e.g., by fast ADMM or Newton algorithms). We demonstrate the merits of graph trend filtering through examples and theory.