Recent work has begun to develop a theory for the representation, processing, and approximation of signals supported on graphs. For signals supported on graphs, the eigenvectors of the graph Laplacian play a role analogous to the Fourier transform. We discuss recent results which develop uncertainty principles for signals supported on graphs, focusing on the role of the graph topology. We then conduct a series of experiments to explore how characteristics of the graph topology influence the extent to which a signal can have low graph spread and spectral spread, as quantified through the uncertainty curve. Through experiments with small-world random graphs, we find a correlation between the clustering coefficient of the graph, the second largest eigenvalue, and the shape of the uncertainty curve.

Date Published: 26 September 2013
PDF: 10 pages
Proc. SPIE 8858, Wavelets and Sparsity XV, 88581K (26 September 2013); doi: 10.1117/12.2024716

Published in SPIE Proceedings Vol. 8858:
Wavelets and Sparsity XV
Dimitri Van De Ville; Vivek K. Goyal; Manos Papadakis, Editor(s)