Trend Filtering on Graphs
arXiv:1410.7690
Abstract
We introduce a family of adaptive estimators on graphs, based on penalizing the 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 -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.
arXiv commentA short version appeared in AISTATS'2015
References in corpus (4)
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- A nearly-mlogn time solver for SDD linear systems
- Modular proximal optimization for multidimensional total-variation regularization
- Detecting Anomalous Activity on Networks with the Graph Fourier Scan Statistic
Cited by in corpus (11)
- Multiscale spatial density smoothing: an application to large-scale radiological survey and anomaly detection
- Learning on Hypergraphs with Sparsity
- Prediction models for network-linked data
- Detecting Localized Categorical Attributes on Graphs
- Better Conditional Density Estimation for Neural Networks
- Nonparametric density estimation by histogram trend filtering
- MOCCA: mirrored convex/concave optimization for nonconvex composite functions
- Interpretable Low-Dimensional Regression via Data-Adaptive Smoothing
- Joint Estimation of Precision Matrices in Heterogeneous Populations
- High-dimensional Gaussian graphical model for network-linked data
- GapTV: Accurate and Interpretable Low-Dimensional Regression and Classification