Trend Filtering on Graphs
Abstract
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.
Cite
Text
Wang et al. "Trend Filtering on Graphs." Journal of Machine Learning Research, 2016.Markdown
[Wang et al. "Trend Filtering on Graphs." Journal of Machine Learning Research, 2016.](https://mlanthology.org/jmlr/2016/wang2016jmlr-trend/)BibTeX
@article{wang2016jmlr-trend,
title = {{Trend Filtering on Graphs}},
author = {Wang, Yu-Xiang and Sharpnack, James and Smola, Alexander J. and Tibshirani, Ryan J.},
journal = {Journal of Machine Learning Research},
year = {2016},
pages = {1-41},
volume = {17},
url = {https://mlanthology.org/jmlr/2016/wang2016jmlr-trend/}
}