Signal Recovery on Graphs: Variation Minimization

Siheng Chen, Aliaksei Sandryhaila, Jose M.F. Moura, Jelena Kovacevic

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number7117446
Pages (from-to)4609-4624
Number of pages16
JournalIEEE Transactions on Signal Processing
Issue number17
StatePublished - Sep 1 2015


  • Matrix completion
  • Semi-supervised learning
  • Signal processing on graphs
  • Signal recovery

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Signal Recovery on Graphs: Variation Minimization'. Together they form a unique fingerprint.

Cite this