# Signal Recovery on Graphs: Variation Minimization

arXiv: https://arxiv.org/abs/1411.7414 · HTML: https://mlsanity.com/paper/1411.7414/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2014.

## Built on by (most cited first, 26 of 26)

- [Graph Signal Restoration Using Nested Deep Algorithm Unrolling](https://mlsanity.com/paper/2106.15910/) (2021)
- [Signal processing on simplicial complexes](https://mlsanity.com/paper/2106.07471/) (2021)
- [Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction](https://mlsanity.com/paper/2403.19800/) (2024)
- [Robust Graph Representation Learning for Local Corruption Recovery](https://mlsanity.com/paper/2202.04936/) (2022)
- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Joint Signal Recovery and Graph Learning from Incomplete Time-Series](https://mlsanity.com/paper/2312.16940/) (2023)
- [Multilinear Kernel Regression and Imputation via Manifold Learning](https://mlsanity.com/paper/2402.03648/) (2024)
- [Robust Offline Active Learning on Graphs](https://mlsanity.com/paper/2408.07941/) (2024)
- [Imputation of Time-varying Edge Flows in Graphs by Multilinear Kernel Regression and Manifold Learning](https://mlsanity.com/paper/2409.05135/) (2024)
- [Graphmax for Text Generation](https://mlsanity.com/paper/2101.00153/) (2021)
- [Retinex-based Image Denoising / Contrast Enhancement using Gradient Graph Laplacian Regularizer](https://mlsanity.com/paper/2307.02625/) (2023)
- [Heterogeneous Graph Structure Learning through the Lens of Data-generating Processes](https://mlsanity.com/paper/2503.08760/) (2025)
- [Missing Data in Signal Processing and Machine Learning: Models, Methods and Modern Approaches](https://mlsanity.com/paper/2506.01696/) (2025)
- [When Do We Need Graph Neural Networks for Node Classification?](https://mlsanity.com/paper/2210.16979/) (2022)
- [Learning Optimal Graph Filters for Clustering of Attributed Graphs](https://mlsanity.com/paper/2211.04634/) (2022)
- [Distributional Signals for Node Classification in Graph Neural Networks](https://mlsanity.com/paper/2304.03507/) (2023)
- [Inhomogeneous graph trend filtering via a l2,0 cardinality penalty](https://mlsanity.com/paper/2304.05223/) (2023)
- [DPC: Unsupervised Deep Point Correspondence via Cross and Self Construction](https://mlsanity.com/paper/2110.08636/) (2021)
- [Stratified Graph Spectra](https://mlsanity.com/paper/2201.03696/) (2022)
- [Unsupervised Graph Spectral Feature Denoising for Crop Yield Prediction](https://mlsanity.com/paper/2208.02714/) (2022)
- [Joint Data Inpainting and Graph Learning via Unrolled Neural Networks](https://mlsanity.com/paper/2407.11429/) (2024)
- [A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networks](https://mlsanity.com/paper/2410.21006/) (2024)
- [Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast](https://mlsanity.com/paper/2505.13102/) (2025)
- [Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming](https://mlsanity.com/paper/2506.01826/) (2025)
- [Robust Spatiotemporally Contiguous Anomaly Detection Using Tensor Decomposition](https://mlsanity.com/paper/2510.00460/) (2025)
- [Filter Learning for Subgraphs: Algebras and Performance Risk Bounds](https://mlsanity.com/paper/2607.21263/) (2026)

## Abstract (arXiv)

We consider the problem of signal recovery on graphs as graphs model data with complex structure as signals on a graph. Graph signal recovery implies recovery of one or multiple smooth graph signals from noisy, corrupted, or incomplete measurements. We propose a graph signal model and formulate signal recovery as a corresponding optimization problem. We provide a general solution by using the alternating direction methods of multipliers. We next show how signal inpainting, matrix completion, robust principal component analysis, and anomaly detection all relate to graph signal recovery, and provide corresponding specific solutions and theoretical analysis. Finally, we validate the proposed methods on real-world recovery problems, including online blog classification, bridge condition identification, temperature estimation, recommender system, and expert opinion combination of online blog classification.