Trend Filtering on Graphs

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 both examples and theory. [abs] [ pdf ][ bib ] &copy JMLR 2016. ( edit, beta )

Authors

• Yu-Xiang Wang
• James Sharpnack
• Alexander J. Smola
• Ryan J. Tibshirani

Keywords

No keywords are indexed for this paper.