TY - JOUR

T1 - Filtering Random Graph Processes over Random Time-Varying Graphs

AU - Isufi, Elvin

AU - Loukas, Andreas

AU - Simonetto, Andrea

AU - Leus, Geert

N1 - Accepted Author Manuscript

PY - 2017/5/18

Y1 - 2017/5/18

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

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

KW - graph filters

KW - graph signal denoising

KW - graph sparsification

KW - random graph signals

KW - random graphs

KW - Signal processing on graphs

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

UR - http://resolver.tudelft.nl/uuid:60b44e91-6dc3-4269-a673-1a8b4cb29d82

U2 - 10.1109/TSP.2017.2706186

DO - 10.1109/TSP.2017.2706186

M3 - Article

AN - SCOPUS:85028396931

VL - 65

SP - 4406

EP - 4421

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 16

M1 - 7931690

ER -