Efficient Graph Signal Recovery over Big Networks

Gabor Hannak; Peter Berger; Gerald Matz; Alex Jung

doi:10.1109/ACSSC.2016.7869702

Efficient Graph Signal Recovery over Big Networks

Gabor Hannak, Peter Berger, Gerald Matz, Alex Jung

Technische Universität Wien

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

2 Citations (Scopus)

Abstract

We consider the problem of recovering a smooth graph signal from noisy samples taken at a small number of graph nodes. The recovery problem is formulated as a convex optimization problem which minimizes the total variation (accounting for the smoothness of the graph signal) while controlling the empirical error. We solve this total variation minimization problem efficiently by applying a recent algorithm proposed by Nesterov for non-smooth optimization problems. Furthermore , we develop a distributed implementation of our algorithm and verify the performance of our scheme on a large-scale real-world dataset.

Original language	English
Title of host publication	Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016
Publisher	IEEE
Pages	1839-1843
Number of pages	5
ISBN (Electronic)	9781538639542
DOIs	https://doi.org/10.1109/ACSSC.2016.7869702
Publication status	Published - 1 Mar 2017
MoE publication type	A4 Conference publication
Event	Asilomar Conference on Signals, Systems & Computers - Pasific Grove, United States Duration: 6 Nov 2016 → 9 Nov 2016 Conference number: 50 http://www.asilomarsscconf.org/

Publication series

Name	Conference Record of the Asilomar Conference on Signals Systems and Computers
ISSN (Print)	1058-6393

Conference

Conference	Asilomar Conference on Signals, Systems & Computers
Abbreviated title	ASILOMAR
Country/Territory	United States
City	Pasific Grove
Period	06/11/2016 → 09/11/2016
Internet address	http://www.asilomarsscconf.org/

Access to Document

10.1109/ACSSC.2016.7869702

Cite this

@inproceedings{fbfd1c72b4894c4c94d58ab861cdba09,

title = "Efficient Graph Signal Recovery over Big Networks",

abstract = "We consider the problem of recovering a smooth graph signal from noisy samples taken at a small number of graph nodes. The recovery problem is formulated as a convex optimization problem which minimizes the total variation (accounting for the smoothness of the graph signal) while controlling the empirical error. We solve this total variation minimization problem efficiently by applying a recent algorithm proposed by Nesterov for non-smooth optimization problems. Furthermore , we develop a distributed implementation of our algorithm and verify the performance of our scheme on a large-scale real-world dataset.",

author = "Gabor Hannak and Peter Berger and Gerald Matz and Alex Jung",

year = "2017",

month = mar,

day = "1",

doi = "10.1109/ACSSC.2016.7869702",

language = "English",

series = "Conference Record of the Asilomar Conference on Signals Systems and Computers",

publisher = "IEEE",

pages = "1839--1843",

booktitle = "Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016",

address = "United States",

note = "Asilomar Conference on Signals, Systems & Computers, ASILOMAR ; Conference date: 06-11-2016 Through 09-11-2016",

url = "http://www.asilomarsscconf.org/",

}

Hannak, G, Berger, P, Matz, G & Jung, A 2017, Efficient Graph Signal Recovery over Big Networks. in Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016., 7869702, Conference Record of the Asilomar Conference on Signals Systems and Computers, IEEE, pp. 1839-1843, Asilomar Conference on Signals, Systems & Computers, Pasific Grove, California, United States, 06/11/2016. https://doi.org/10.1109/ACSSC.2016.7869702

Efficient Graph Signal Recovery over Big Networks. / Hannak, Gabor; Berger, Peter; Matz, Gerald et al.
Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. IEEE, 2017. p. 1839-1843 7869702 (Conference Record of the Asilomar Conference on Signals Systems and Computers).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Efficient Graph Signal Recovery over Big Networks

AU - Hannak, Gabor

AU - Berger, Peter

AU - Matz, Gerald

AU - Jung, Alex

N1 - Conference code: 50

PY - 2017/3/1

Y1 - 2017/3/1

N2 - We consider the problem of recovering a smooth graph signal from noisy samples taken at a small number of graph nodes. The recovery problem is formulated as a convex optimization problem which minimizes the total variation (accounting for the smoothness of the graph signal) while controlling the empirical error. We solve this total variation minimization problem efficiently by applying a recent algorithm proposed by Nesterov for non-smooth optimization problems. Furthermore , we develop a distributed implementation of our algorithm and verify the performance of our scheme on a large-scale real-world dataset.

AB - We consider the problem of recovering a smooth graph signal from noisy samples taken at a small number of graph nodes. The recovery problem is formulated as a convex optimization problem which minimizes the total variation (accounting for the smoothness of the graph signal) while controlling the empirical error. We solve this total variation minimization problem efficiently by applying a recent algorithm proposed by Nesterov for non-smooth optimization problems. Furthermore , we develop a distributed implementation of our algorithm and verify the performance of our scheme on a large-scale real-world dataset.

U2 - 10.1109/ACSSC.2016.7869702

DO - 10.1109/ACSSC.2016.7869702

M3 - Conference article in proceedings

T3 - Conference Record of the Asilomar Conference on Signals Systems and Computers

SP - 1839

EP - 1843

BT - Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016

PB - IEEE

T2 - Asilomar Conference on Signals, Systems & Computers

Y2 - 6 November 2016 through 9 November 2016

ER -

Efficient Graph Signal Recovery over Big Networks

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this