Survey Lecture: Michael Schaub: Signal processing on graphs and complexes

Tuesday, April 19, 2022, 4:30pm

Location: Department of Computer Science, Ahornstr. 55, building E2 (no. 2356), ground floor, room: B-IT 5053.2. and as online session

Speaker:  Michael Schaub

 

Abstract:

Graph signal processing (GSP) tries to device appropriate tools to process signals supported on graphs by generalizing classical methods from signal processing of time-series and images -- such as smoothing, filtering and interpolation of signals supported on the nodes of a graph.  Typically, this involves leveraging the structure of the graph as encoded in the spectral properties of the graph Laplacian.
In certain scenarios, such as traffic network analysis, the signals of interest are however naturally defined on the edges of a graph, rather than on the nodes. After a brief recap of the central ideas of GSP, we examine why standard tools from GSP may not be suitable for the analysis of such edge signals.  More specifically, we discuss how the underlying notion of 'signal vs noise' inherited from typically considered variants of the graph Laplacian are not suitable when dealing with edge signals that encode flows.  To overcome this limitation, we devise signal processing tools based on the Hodge-Laplacian and the associated discrete Hodge Theory for simplicial (and cellular) complexes.  We discuss applications of these ideas for signal smoothing, semi-supervised and active learning for edge-flows on discrete or discretized spaces.