Signal Recovery on Graphs: Variation Minimization

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

doi:10.1109/TSP.2015.2441042

Signal Recovery on Graphs: Variation Minimization

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

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English (US)
Article number	7117446
Pages (from-to)	4609-4624
Number of pages	16
Journal	IEEE Transactions on Signal Processing
Volume	63
Issue number	17
DOIs	https://doi.org/10.1109/TSP.2015.2441042
State	Published - Sep 1 2015

Keywords

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

ASJC Scopus subject areas

Signal Processing
Electrical and Electronic Engineering

Access to Document

10.1109/TSP.2015.2441042

Cite this

@article{a318d16bf7974fe28d479e93ad55dc83,

title = "Signal Recovery on Graphs: Variation Minimization",

abstract = "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.",

keywords = "Matrix completion, Semi-supervised learning, Signal processing on graphs, Signal recovery",

author = "Siheng Chen and Aliaksei Sandryhaila and Moura, {Jose M.F.} and Jelena Kovacevic",

note = "Publisher Copyright: {\textcopyright} 1991-2012 IEEE.",

year = "2015",

month = sep,

day = "1",

doi = "10.1109/TSP.2015.2441042",

language = "English (US)",

volume = "63",

pages = "4609--4624",

journal = "IEEE Transactions on Signal Processing",

issn = "1053-587X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "17",

}

TY - JOUR

T1 - Signal Recovery on Graphs

T2 - Variation Minimization

AU - Chen, Siheng

AU - Sandryhaila, Aliaksei

AU - Moura, Jose M.F.

AU - Kovacevic, Jelena

PY - 2015/9/1

Y1 - 2015/9/1

N2 - 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.

AB - 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.

KW - Matrix completion

KW - Semi-supervised learning

KW - Signal processing on graphs

KW - Signal recovery

UR - http://www.scopus.com/inward/record.url?scp=84939163707&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84939163707&partnerID=8YFLogxK

U2 - 10.1109/TSP.2015.2441042

DO - 10.1109/TSP.2015.2441042

M3 - Article

AN - SCOPUS:84939163707

SN - 1053-587X

VL - 63

SP - 4609

EP - 4624

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

IS - 17

M1 - 7117446

ER -

Signal Recovery on Graphs: Variation Minimization

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this