Vector-Valued Graph Trend Filtering with Non-Convex Penalties

Abstract

This work studies the denoising of piecewise smooth graph signals that exhibit inhomogeneous levels of smoothness over a graph, where the value at each node can be vector-valued. We extend the graph trend filtering framework to denoising vector-valued graph signals with a family of non-convex regularizers, which exhibit superior recovery performance over existing convex regularizers. Using an oracle inequality, we establish the statistical error rates of first-order stationary points of the proposed non-convex method for generic graphs. Furthermore, we present an ADMM-based algorithm to solve the proposed method and establish its convergence. Numerical experiments are conducted on both synthetic and real-world data for denoising, support recovery, event detection, and semi-supervised classification.

arXiv commentThe first two authors contributed equally

References in corpus (24)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Nearly unbiased variable selection under minimax concave penalty
• OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks
• Discrete Signal Processing on Graphs
• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• On the conditions used to prove oracle results for the Lasso
• Discrete Signal Processing on Graphs: Sampling Theory
• Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection
• The solution path of the generalized lasso
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• Signal Recovery on Graphs: Variation Minimization
• A Selective Review of Group Selection in High-Dimensional Models
• Network Lasso: Clustering and Optimization in Large Graphs
• Adaptive piecewise polynomial estimation via trend filtering
• Kernel-based Reconstruction of Graph Signals
• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• On the Prediction Performance of the Lasso
• Optimal rates for total variation denoising
• Signal Representations on Graphs: Tools and Applications
• Approximate Recovery in Changepoint Problems, from ${\ell }_2$ Estimation Error Rates
• Rank Awareness in Joint Sparse Recovery
• Semi-Supervised Learning via Sparse Label Propagation
• Learning Latent Features with Pairwise Penalties in Low-Rank Matrix Completion
• When is Network Lasso Accurate: The Vector Case

Cited by in corpus (4)

• Graph Unrolling Networks: Interpretable Neural Networks for Graph Signal Denoising
• Learning Latent Features with Pairwise Penalties in Low-Rank Matrix Completion
• Learning Multi-Attribute Differential Graphs with Non-Convex Penalties
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models