Data sampling on graphs

Details

Supervisors

Delvenne, Jean-Charles

Faculty

Ecole polytechnique de Louvain

Degree label

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

Abstract

This master thesis focuses on proposing techniques to sample data defined on a graph and solving several related problems. We started by reviewing the building blocks of Graph Signal Processing and giving a first attempt to model and sample spatiotemporal data. We then considered conservative flows associated with the edges of a graph and devised algorithms to sample and perfectly recover such data signals using cycle spaces. An alternative sampling procedure based on the aggregation of the flow around cycles has also been proposed, and we designed an algorithm based on the greedy matroid algorithm to minimize the cost of that procedure. Moreover, we showed how to deal with noisy observations through the newly introduced concept of fundamental basis number. Finally, we extended the Mac Lane's planarity criterion to this fundamental basis number in order to characterize a certain class of graphs, the hole-free graphs.