Match!

Discrete Signal Processing on Graphs: Sampling Theory

Published on Dec 1, 2015in IEEE Transactions on Signal Processing5.23
· DOI :10.1109/TSP.2015.2469645
Siheng Chen15
Estimated H-index: 15
(CMU: Carnegie Mellon University),
Rohan Varma6
Estimated H-index: 6
(CMU: Carnegie Mellon University)
+ 1 AuthorsJelena Kovacevic39
Estimated H-index: 39
(CMU: Carnegie Mellon University)
View in Source
Abstract
We propose a sampling theory for signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that perfect recovery is possible for graph signals bandlimited under the graph Fourier transform. The sampled signal coefficients form a new graph signal, whose corresponding graph structure preserves the first-order difference of the original graph signal. For general graphs, an optimal sampling operator based on experimentally designed sampling is proposed to guarantee perfect recovery and robustness to noise; for graphs whose graph Fourier transforms are frames with maximal robustness to erasures as well as for Erdős-Renyi graphs, random sampling leads to perfect recovery with high probability. We further establish the connection to the sampling theory of finite discrete-time signal processing and previous work on signal recovery on graphs. To handle full-band graph signals, we propose a graph filter bank based on sampling theory on graphs. Finally, we apply the proposed sampling theory to semi-supervised classification of online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.
Figures & Tables
  • References (64)
  • Citations (263)
References64
Newest
#1Siheng ChenH-Index: 15
#2Aliaksei Sandryhaila (CMU: Carnegie Mellon University)H-Index: 18
Last.Jelena KovacevicH-Index: 39
view all 4 authors...
105 CitationsSource
#1Xiaohan Wang (THU: Tsinghua University)H-Index: 8
#2Mengdi Wang (Princeton University)H-Index: 12
Last.Gu Yuantao (THU: Tsinghua University)H-Index: 17
view all 3 authors...
35 CitationsSource
#1Siheng Chen (CMU: Carnegie Mellon University)H-Index: 15
#2Rohan Varma (CMU: Carnegie Mellon University)H-Index: 6
Last.Jelena Kovacevic (CMU: Carnegie Mellon University)H-Index: 39
view all 4 authors...
22 CitationsSource
#1Xiaohan Wang (THU: Tsinghua University)H-Index: 8
#2Pengfei Liu (THU: Tsinghua University)H-Index: 5
Last.Gu Yuantao (THU: Tsinghua University)H-Index: 17
view all 3 authors...
106 CitationsSource
Apr 1, 2015 in ICASSP (International Conference on Acoustics, Speech, and Signal Processing)
#1Akshay Gadde (SC: University of Southern California)H-Index: 9
#2Antonio Ortega Diego (SC: University of Southern California)H-Index: 52
33 CitationsSource
Apr 1, 2015 in ICASSP (International Conference on Acoustics, Speech, and Signal Processing)
#1Siheng Chen (CMU: Carnegie Mellon University)H-Index: 15
#2Aliaksei Sandryhaila (CMU: Carnegie Mellon University)H-Index: 18
Last.Jelena Kovacevic (CMU: Carnegie Mellon University)H-Index: 39
view all 3 authors...
28 CitationsSource
#1Ha Q. Nguyen (UIUC: University of Illinois at Urbana–Champaign)H-Index: 5
#2Minh N. Do (UIUC: University of Illinois at Urbana–Champaign)H-Index: 48
55 CitationsSource
#1Siheng Chen (CMU: Carnegie Mellon University)H-Index: 15
Last.Jelena Kovacevic (CMU: Carnegie Mellon University)H-Index: 39
view all 4 authors...
53 CitationsSource
#1Martin VettedH-Index: 91
#2Jelena KovacevicH-Index: 39
Last.Vivek K. GoyalH-Index: 41
view all 3 authors...
85 Citations
75 CitationsSource
Cited By263
Newest
#1Marcelo Jorge Mendes Spelta (UFRJ: Federal University of Rio de Janeiro)H-Index: 1
#2Wallace A. Martins (UFRJ: Federal University of Rio de Janeiro)H-Index: 10
Source
#1Bruno Scalzo DeesH-Index: 1
#2Ljubisa StankovicH-Index: 39
Last.Danilo P. MandicH-Index: 48
view all 5 authors...
#1Fen Wang (Xidian University)H-Index: 2
#2Yongchao Wang (Xidian University)H-Index: 4
Last.Cheng Yang (York University)
view all 4 authors...
#1Yu Zhu (Rice University)H-Index: 1
#2Fernando J. Iglesias (URJC: King Juan Carlos University)H-Index: 1
Last.Santiago Segarra (Rice University)H-Index: 15
view all 4 authors...
#1Xuan XieH-Index: 1
Last.Bo Hu (Fudan University)H-Index: 12
view all 4 authors...
#2Xuan XieH-Index: 1
Last.Bo Hu (Fudan University)H-Index: 12
view all 4 authors...
#1Kun Yan (GUET: Guilin University of Electronic Technology)H-Index: 6
#2Hsiao-Chun Wu (LSU: Louisiana State University)H-Index: 23
Last.Xiangli Zhang (GUET: Guilin University of Electronic Technology)H-Index: 2
view all 4 authors...
Source
#1Alejandro Parada (UD: University of Delaware)H-Index: 3
#2Daniel L. Lau (UK: University of Kentucky)H-Index: 21
Last.Gonzalo R. Arce (UD: University of Delaware)H-Index: 45
view all 4 authors...
2 CitationsSource
#1Yoon Hak Kim (Chosun University)H-Index: 3
#2Antonio Ortega Diego (SC: University of Southern California)H-Index: 52
1 CitationsSource
View next paperSignal Recovery on Graphs: Variation Minimization