230521
20190317000811.0
1053-587X
10.1109/Tsp.2017.2706186
doi
000404286900019
ISI
ARTICLE
Filtering Random Graph Processes Over Random Time-Varying Graphs
Piscataway
2017
Institute of Electrical and Electronics Engineers
2017
16
Journal Articles
Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deterministic setting, ignoring the impact of stochasticity in both the graph topology and the signal itself. To bridge this gap, we examine the statistical behavior of the two key filter types, finite impulse response and autoregressive moving average graph filters, when operating on random time-varying graph signals (or random graph processes) over random time-varying graphs. Our analysis shows that 1) in expectation, the filters behave as the same deterministic filters operating on a deterministic graph, being the expected graph, having as input signal a deterministic signal, being the expected signal, and 2) there are meaningful upper bounds for the variance of the filter output. We conclude this paper by proposing two novel ways of exploiting randomness to improve (joint graph-time) noise cancellation, as well as to reduce the computational complexity of graph filtering. As demonstrated by numerical results, these methods outperform the disjoint average and denoise algorithm and yield a (up to) four times complexity reduction, with a very little difference from the optimal solution.
Signal processing on graphs
graph filters
random graphs
random graph signals
graph signal denoising
graph sparsification
Isufi, Elvin
Delft Univ Technol, Fac Elect Engn Math & Comp Sci, NL-2826 CD Delft, Netherlands
Loukas, Andreas
Swiss Fed Inst Technol Lausanne, Fac Elect Engn, CH-1015 Lausanne, Switzerland
266654
249911
Simonetto, Andrea
Leus, Geert
Delft Univ Technol, Fac Elect Engn Math & Comp Sci, NL-2826 CD Delft, Netherlands
4406-4421
16
Ieee Transactions On Signal Processing
65
Preprint
2260372
Preprint
http://infoscience.epfl.ch/record/230521/files/main.pdf
LTS2
252392
U10380
252393
LTS4
U10851
oai:infoscience.tind.io:230521
article
STI
GLOBAL_SET
266654
EPFL-ARTICLE-230521
EPFL
PUBLISHED
REVIEWED
ARTICLE