Signal processing and random walks on simplicial complexes

In many applications, we are confronted with with signals defined on the nodes of a graph.
Think for instance of a sensor network measuring temperature; or a social network, in which each person has an opinion about a specific issue.
Graph signal processing (GSP) tries to device appropriate tools to process such data by generalizing classical methods from signal processing of time-series and images — such as smoothing, filtering and interpolation — to signals defined on graphs.
Typically, this involves leveraging the structure of the graph as encoded in the spectral properties of the graph Laplacian.
In applications such as traffic network analysis, however, the signals of interest are naturally defined on the edges of a graph, rather than on the nodes.
After a brief introduction to the ideas of GSP, we examine why the standard tools from GSP may not be suitable for the analysis of such edge signals.
More specifically, we discuss how the underlying notion of a ‘smooth signal’ inherited from (the typically considered variants of) the graph Laplacian are not suitable when dealing with edge signals that encode a notion of flow.
To overcome this limitation we devise signal processing tools based on the Hodge 1-Laplacian and discrete Hodge Theory.
We first discuss how these tools can be applied for signal smoothing, semi-supervised and active learning for edge-signals on graphs.
We then explore connections of these signal processing tools to random walks on graphs and simplicial complexes, and give alternative interpretations of our previously derived methods in terms of diffusion processes on simplicial complexes.

Speaker: Michael Schaub, University of Oxford

More information can be found on the seminar's webpage: https://www.epfl.ch/labs/hessbellwald-lab/seminar/apptopsem1920/