Uncertainty principles for signals defined on graphs: Bounds and characterizations

Ameya Agaskar, Yue M. LuICASSP 2012 · OpenReview

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.
BibTeX
@inproceedings{agaskar2012uncertainty,
  author = {Ameya Agaskar and Yue M. Lu},
  title = {{Uncertainty principles for signals defined on graphs: Bounds and characterizations}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2012},
  url = {https://openreview.net/forum?id=smblVN9Ze1e},
}

Loading related content...

Figure