, , ,

I am preparing material for the upcoming Peyresq summer school on signal processing in high dimensions. My lectures will cover the emerging field of signal processing on graphs, following a rather classical approach based on harmonic analysis. By harmonic analysis on graphs or networks, I really mean building on the spectral theory of the graph Laplacian to construct a coherent data processing framework. It allows us to understand localisation, smoothness, to filter and construct multiscale transforms (i.e wavelets), all this on generic graphs and networks therefore generalising many familiar concepts from signal processing. These tools can then be used for applications like de-noising, missing data imputation, machine learning, building recommender systems etc …

Here is in more details what I plan to cover, in five lectures:

  1. I introduce the graph Laplacian \mathcal{L}, it’s spectral theory and the associated Borel functional calculus. I’ll quickly discuss other discrete differential operators (gradient, divergence). These can be viewed as linear operators acting on signals defined at the vertices of the graph. I use them to characterise the smoothness of signals and explain how spectral graph theory is used for clustering, finding embeddings (Laplacian eigenmaps). I conclude by designing a de-noising framework based on Tikhonov regularisation that hints at the idea of graph filters defined on the spectral domain.
  2. In the second lecture I define more formally spectral kernels and how they are used to construct a kernel localisation operator  that acts like a convolution. I detail the fundamental limits on the localisation one can obtain based on the smoothness of the generating kernel.
  3. In the third lecture I describe the construction of wavelets on graphs and provide an efficient algorithm to implement the wavelet transform. I highlight some applications to machine learning (transductive learning), recommender systems but also to processing point clouds. I also introduce a Gabor-like transform and discuss its use in constructing an uncertainty principle.
  4. The fourth lecture is devoted to a multiscale framework unifying wavelets, interpolation on graphs with operations such as coarsening and sparsification .
  5. The fifth lecture is devoted to results linking spectral graph theory to the spectral theory of the Laplace-Beltrami operator and why this is interesting in manifold learning for instance.