The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
A Spectral Graph Uncertainty Principle
Open accessAbstract
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 ε by a fast approximation algorithm requiringO(ε-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 Erd-s-Rényi 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Non-Local Algorithm for Image Denoising
Buades, A., Coll, B., & Morel, J.-M. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.38 · Cited by 7,616
Newman, M. (2010) · doi:10.1093/acprof:oso/9780199206650.001.0001 · Cited by 6,595
Cited by
Graph Signal Processing: Overview, Challenges, and Applications
Ortega, A., Frossard, P., Kovačević, J., Moura, J. M. F., & Vandergheynst, P. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2820126 · Cited by 1,787
Discrete Signal Processing on Graphs
Sandryhaila, A., & Moura, J. M. F. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2238935 · Cited by 1,531
Discrete Signal Processing on Graphs: Frequency Analysis
Sandryhaila, A., & Moura, J. M. F. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2321121 · Cited by 879
Discrete Signal Processing on Graphs: Sampling Theory
Chen, S., Varma, R., Sandryhaila, A., & Kovacevic, J. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2469645 · Cited by 666
Learning Laplacian Matrix in Smooth Graph Signal Representations
Dong, X., Thanou, D., Frossard, P., & Vandergheynst, P. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2602809 · Cited by 640
Metadata
- Authors
- Agaskar, A., & Lu, Y. M.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2013-07
- Volume
- 59
- Issue
- 7
- Pages
- 4338-4356
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2111160863
- Cited by
- 167
- References
- 2
- FWCI
- 38.68
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: A Spectral Graph Uncertainty Principle. https://app.cochat.ai/papers/10.1109/tit.2013.2252233
- The paper
- Agaskar, A., & Lu, Y. M. (2013). A Spectral Graph Uncertainty Principle. IEEE Transactions on Information Theory. https://doi.org/10.1109/tit.2013.2252233
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.