Abstract
The necessity to process signals living in nonEuclidean domains, such as signals defined on the top of a graph, has led to the extension of signal processing techniques to the graph setting. Among different approaches, graph signal processing distinguishes itself by providing a Fourier analysis of these signals. Analogously to the Fourier transform for time and image signals, the graph Fourier transform decomposes the graph signals decomposes in terms of the harmonics provided by the underlying topology. For instance, a graph signal characterized by a slow variation between adjacent nodes has a low frequency content.
Along with the graph Fourier transform, graph filters are the key tool to alter the graph frequency content of a graph signal. This thesis focuses on graph filters that are performed distributively in the node domain–that is, each node needs to exchange information only within its neighbor to perform a given filtering operation. Similarly to the classical filters, we propose ways to design and implement distributed finite impulse response and infinite impulse response graph filters.
One of the key contributions of this thesis is to bring the temporal dimension to graph signal processing and build upon a graphtime signal processing framework. This is done in different ways. First, we analyze the effects that the temporal variations on the graph signal and graph topology have on the filtering output. Second, we introduce the notion of joint graphtime filtering. Third, we presentpr a statistical analysis of the distributed graph filtering when the graph signal and the graph topology change randomly in time. Finally, we extend the sampling framework from the reconstruction of graph signals to the observation and tracking of timevarying graph processes.
We characterize the behavior of the distributed autoregressivemoving average (ARMA) graph filters when the graph signal and the graph topology are timevarying. The latter analysis is exploited in two ways: i ) to quantify the limitations of graph filters in a dynamic environment, such as a moving sensors processing a timevarying signal in a sensor network; and i i ) to provide ways for filtering with low computation and communication complexity timevarying graph signals.
We develop the notion of distributed graphtime filtering, which is an operation that jointly processes the graph frequencies of a timevarying graph signal on one hand and its temporal frequencies on the other hand. We propose distributed finite impulse response and infinite impulse response recursions to implement a twodimensional graphtime filtering operation. Finally, we propose design strategies to find the filter coefficients that approximate a desired twodimensional frequency response.
We extend the analysis of graph filters to a stochastic environment, i.e., when the graph topology and the graph signal change randomly over time. By characterizing the first and second order moments of the filter output, we quantify the impact of the graph signal and the graph topology randomness into the distributed filtering operation. The latter allows us to develop the notion of graph filtering in the mean, which is also used to ease the computational burden of classical graph filters.
Finally, we propose a sampling framework for timevarying graph signals. Particularly, when the graph signal changes over time following a statespace model, we extend the graph signal sampling theory to the tasks of observing and tracking the timevarying graph signal froma few relevant nodes. The latter theory considers the graph signal sampling as a particular case and shows that tools from sparse sensing and sensor selection can be used for sampling.
Along with the graph Fourier transform, graph filters are the key tool to alter the graph frequency content of a graph signal. This thesis focuses on graph filters that are performed distributively in the node domain–that is, each node needs to exchange information only within its neighbor to perform a given filtering operation. Similarly to the classical filters, we propose ways to design and implement distributed finite impulse response and infinite impulse response graph filters.
One of the key contributions of this thesis is to bring the temporal dimension to graph signal processing and build upon a graphtime signal processing framework. This is done in different ways. First, we analyze the effects that the temporal variations on the graph signal and graph topology have on the filtering output. Second, we introduce the notion of joint graphtime filtering. Third, we presentpr a statistical analysis of the distributed graph filtering when the graph signal and the graph topology change randomly in time. Finally, we extend the sampling framework from the reconstruction of graph signals to the observation and tracking of timevarying graph processes.
We characterize the behavior of the distributed autoregressivemoving average (ARMA) graph filters when the graph signal and the graph topology are timevarying. The latter analysis is exploited in two ways: i ) to quantify the limitations of graph filters in a dynamic environment, such as a moving sensors processing a timevarying signal in a sensor network; and i i ) to provide ways for filtering with low computation and communication complexity timevarying graph signals.
We develop the notion of distributed graphtime filtering, which is an operation that jointly processes the graph frequencies of a timevarying graph signal on one hand and its temporal frequencies on the other hand. We propose distributed finite impulse response and infinite impulse response recursions to implement a twodimensional graphtime filtering operation. Finally, we propose design strategies to find the filter coefficients that approximate a desired twodimensional frequency response.
We extend the analysis of graph filters to a stochastic environment, i.e., when the graph topology and the graph signal change randomly over time. By characterizing the first and second order moments of the filter output, we quantify the impact of the graph signal and the graph topology randomness into the distributed filtering operation. The latter allows us to develop the notion of graph filtering in the mean, which is also used to ease the computational burden of classical graph filters.
Finally, we propose a sampling framework for timevarying graph signals. Particularly, when the graph signal changes over time following a statespace model, we extend the graph signal sampling theory to the tasks of observing and tracking the timevarying graph signal froma few relevant nodes. The latter theory considers the graph signal sampling as a particular case and shows that tools from sparse sensing and sensor selection can be used for sampling.
Original language  English 

Awarding Institution 

Supervisors/Advisors 

Award date  28 Jan 2019 
Print ISBNs  9789402813531 
DOIs  
Publication status  Published  2019 
Keywords
 Graph signal processing
 graph filters
 graphtime signal processing
 graphtime filters
 Laplacian
 network theory
 FIR
 ARMA
 observability
 linear system on graphs
 Kalman filter
 sampling theory
 graph sampling
 sparse sensing