Signal Recovery on Graphs: Variation Minimization

By Siheng Chen, Aliaksei Sandryhaila, José M. F. Moura, Jelena Kovacevic. IEEE Transactions on Signal Processing, 2014

298 citations recorded by the source corpus.

We consider the problem of signal recovery on graphs. Graphs model data with complex structure as signals on a graph. Graph signal recovery recovers one or multiple smooth graph signals from noisy, corrupted, or incomplete measurements. We formulate graph signal recovery as an optimization problem, for which we provide a general solution through the alternating direction methods of multipliers. We 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. We validate the proposed methods on real-world recovery problems, including online blog classification, bridge condition identification, temperature estimation, recommender system for jokes, and expert opinion combination of online blog classification.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/21b28c2e5c69439b991ad0539502eaf23329f5f3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Discrete Signal Processing on Graphs: Sampling Theory (2015, background): “Signal recovery on graphs attempts to recover graph signals that are assumed to be smooth with respect to underlying graphs, from noisy, missing, or corrupted samples [23].”
Graph Signal Processing: Overview, Challenges, and Applications (2017, background): “should consider definitions and choose the one that leads to the best trade-off for the problem being considered [82].”
Explainability Methods for Graph Convolutional Neural Networks (2019, background): “…meth-ods for CNNs. Graph Convolutional Neural Networks: The mathematical foundation of GCNNs is deeply rooted in the ﬁeld of graph signal processing [3, 4] and spectral graph theory in which signal operations like Fourier transform and convolutions are extended to signals living on graphs.”