000230521 001__ 230521 000230521 005__ 20190317000811.0 000230521 0247_ $$2doi$$a10.1109/Tsp.2017.2706186 000230521 022__ $$a1053-587X 000230521 02470 $$2ISI$$a000404286900019 000230521 037__ $$aARTICLE 000230521 245__ $$aFiltering Random Graph Processes Over Random Time-Varying Graphs 000230521 260__ $$bInstitute of Electrical and Electronics Engineers$$c2017$$aPiscataway 000230521 269__ $$a2017 000230521 300__ $$a16 000230521 336__ $$aJournal Articles 000230521 520__ $$aGraph 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. 000230521 6531_ $$aSignal processing on graphs 000230521 6531_ $$agraph filters 000230521 6531_ $$arandom graphs 000230521 6531_ $$arandom graph signals 000230521 6531_ $$agraph signal denoising 000230521 6531_ $$agraph sparsification 000230521 700__ $$uDelft Univ Technol, Fac Elect Engn Math & Comp Sci, NL-2826 CD Delft, Netherlands$$aIsufi, Elvin 000230521 700__ $$0249911$$g266654$$uSwiss Fed Inst Technol Lausanne, Fac Elect Engn, CH-1015 Lausanne, Switzerland$$aLoukas, Andreas 000230521 700__ $$aSimonetto, Andrea 000230521 700__ $$aLeus, Geert$$uDelft Univ Technol, Fac Elect Engn Math & Comp Sci, NL-2826 CD Delft, Netherlands 000230521 773__ $$j65$$tIeee Transactions On Signal Processing$$k16$$q4406-4421 000230521 8564_ $$uhttps://infoscience.epfl.ch/record/230521/files/main.pdf$$zPreprint$$s2260372$$yPreprint 000230521 909C0 $$xU10380$$0252392$$pLTS2 000230521 909C0 $$0252393$$xU10851$$pLTS4 000230521 909CO $$qGLOBAL_SET$$pSTI$$particle$$ooai:infoscience.tind.io:230521 000230521 917Z8 $$x266654 000230521 937__ $$aEPFL-ARTICLE-230521 000230521 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL 000230521 980__ $$aARTICLE