@article {33212,
	title = {A Spectral Graph Uncertainty Principle},
	journal = {IEEE Transactions on Information Theory},
	volume = {59},
	number = {7},
	year = {2013},
	pages = {4338-4356},
	abstract = {The spectral theory of graphs provides a bridge between classical signal processing and the nascent field of graph signal processing. In this paper, a spectral graph analogy to Heisenberg{\textquoteright}s celebrated uncertainty principle is developed. Just as the classical result provides a tradeoff between signal localization in time and frequency, this result provides a fundamental tradeoff between a signal{\textquoteright}s localization on a graph and in its spectral domain.\&nbsp;Using the eigenvectors of the graph Laplacian as a surrogate Fourier basis, quantitative definitions of graph and spectral {\textquoteleft}{\textquoteleft}spreads{\textquoteright}{\textquoteright} are given,\&nbsp;and a complete characterization of the feasibility region of these two quantities is developed.\&nbsp;In particular, the lower boundary of the region, referred to as the uncertainty curve,\&nbsp;is shown to be achieved by eigenvectors associated with the smallest eigenvalues of an affine family of matrices. The convexity of the uncertainty curve allows it to be found to within $\varepsilon$ by a fast approximation algorithm requiring $\mathcal{O}(\varepsilon^{-1/2})$ typically sparse eigenvalue evaluations.\&nbsp;Closed-form expressions for the uncertainty curves for some special classes of graphs are derived,\&nbsp;and an accurate analytical approximation for the expected uncertainty curve of Erdos-Renyi random graphs is developed. These theoretical results are validated by numerical experiments, which also reveal an intriguing connection between diffusion processes on graphs and the uncertainty bounds.},
	author = {Ameya Agaskar and Yue M. Lu}
}
