Date Presented:

Aug.

Abstract:

The classical uncertainty principle provides a fundamental tradeoff in the localization of a function in the time
and frequency domains. In this paper we extend this classical result to functions defined on graphs. We justify
the use of the graph Laplacian’s eigenbasis as a surrogate for the Fourier basis for graphs, and define the notions of "spread" in the graph and spectral domains. We then establish an analogous uncertainty principle relating the two quantities, showing the degree to which a function can be simultaneously localized in the graph and spectral domains.

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.