Graph signal processing for time-varying signals issued from linear dynamical systems

Details

Supervisors

Delvenne, Jean-Charles

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées

Abstract

In a world where the amount of data around us has never been so important, collecting data residing on graph structures is an important issue. However, it is often impossible to collect all the data from every node on a graph. In this thesis, we focus on the problem of sampling and reconstruction of time-varying graph signals issued from linear dynamical systems. In the first part, we review the sampling and reconstruction problem for arbitrary static and time-varying graph signals. To solve this problem, the sampling theory uses prior knowledge about the underlying graph structure through the graph shift (adjacency matrix or graph Laplacian) which is one of the building blocks of Graph Signal Processing. No prior knowledge about the underlying dynamic of these signals is usually taken into account. In the second part, we propose a new graph shift which exploits the knowledge we have when signals are issued from linear dynamical systems. We show that this allows to systematically have a sparse representation of the signal in the frequency domain and to put a bound on the sufficient number of nodes to sample for perfect recovery of the whole signal. We find that it improves the performances obtained in sampling and in reconstruction and that using this new graph shift stays efficient in case of noisy or nonlinear signals. Building a dynamical graph based on the dynamic of the signal, we also show how we can identify a valid sampling set by applying some coloring rules. Finally, we show by numerical results how the stability of the linear system has an impact on the optimal sampling strategy to apply.