A Spectral Graph Uncertainty Principle

DOI10.1109/TIT.2013.2252233MaRDI QIDQ5346461zbMATH OpenOpenAlexFDO

Authors Ameya Agaskar, Yue M. Lu

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.6356

Mathematics Subject Classification ID

Applications of graph theory (05C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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'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's localization on a graph and in its spectral domain. Using the eigenvectors of the graph Laplacian as a surrogate Fourier basis, quantitative definitions of graph and spectral "spreads" are given, and a complete characterization of the feasibility region of these two quantities is developed. In particular, the lower boundary of the region, referred to as the uncertainty curve, 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 $O(varepsilo{n}^{-1/2})$ typically sparse eigenvalue evaluations. Closed-form expressions for the uncertainty curves for some special classes of graphs are derived, and an accurate analytical approximation for the expected uncertainty curve of ErdH{o}s-R'enyi 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.

Cited in

(10)

• Signals on graphs: transforms and tomograms
• Random sampling of bandlimited signals on graphs
• Graph Fourier transform based on \(\ell_1\) norm variation minimization
• Tighter uncertainty principles for periodic signals in terms of frequency
• Frequency domain uncertainty and the graph topology
• Graph theoretic uncertainty and feasibility
• Data Analytics on Graphs Part II: Signals on Graphs
• Graph signal processing on dynamic graphs based on temporal-attention product
• A generalization of Gleason's frame function for quantum measurement
• Approximation theorems on graphs

This page was built for publication: A Spectral Graph Uncertainty Principle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346461)