Uncertainty principles for signals defined on graphs: Bounds and characterizations

Citation:

A. Agaskar and Y. M. Lu, “Uncertainty principles for signals defined on graphs: Bounds and characterizations,” in Proc. IEEE International Conference on Acoustics, Speech and Signal Processing, Kyoto, 2012.
graph_icassp12.pdf150 KB

Date Presented:

Mar.

Abstract:

The classical uncertainty principle provides a fundamental tradeoff in the localization of a signal in the time and frequency domains. In this paper we describe a similar tradeoff for signals defined on graphs. We describe the notions of "spread" in the graph and spectral domains, using the eigenvectors of the graph Laplacian as a surrogate Fourier basis. We then describe how to find signals that, among all signals with the same spectral spread, have the smallest graph spread about a given vertex. For every possible spectral spread, the desired signal is the solution to an eigenvalue problem. Since localization in graph and spectral domains is a desirable property of the elements of wavelet frames on graphs, we compare the performance of some existing wavelet transforms to the obtained bound.

Notes:

See, also, the extended journal version: A. Agaskar and Y. M. Lu, A Spectral Graph Uncertainty Principle, IEEE Transactions on Information Theory, to appear.

Last updated on 03/20/2013