Toward an uncertainty principle for weighted graphs
By B. Pasdeloup, Réda Alami, Vincent Gripon, Michael G. Rabbat. 2015
30 citations recorded by the source corpus.
The uncertainty principle states that a signal cannot be localized both in time and frequency. With the aim of extending this result to signals on graphs, Agaskar & Lu introduce notions of graph and spectral spreads. They show that a graph uncertainty principle holds for some families of unweighted graphs. This principle states that a signal cannot be simultaneously localized both in graph and spectral domains. In this paper, we aim to extend their work to weighted graphs. We show that a naive extension of their definitions leads to inconsistent results such as discontinuity of the graph spread when regarded as a function of the graph structure. To circumvent this problem, we propose another definition of graph spread that relies on an inverse similarity matrix. We also discuss the choice of the distance function that appears in this definition. Finally, we compute and plot uncertainty curves for families of weighted graphs.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical and Nonlinear Physics, Graph Learning, Information Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Pierre Vandergheynst
- Pascal Frossard
- Xavier Bresson
- Nathanael Perraudin
- Michaël Defferrard
- Antonio Ortega
- Michael M. Bronstein
- José M. F. Moura
In Computational Theory and Mathematics
- Pierre Vandergheynst
- Nathanael Perraudin
- David I. Shuman
- José M. F. Moura
- Antonio Ortega
- Pascal Frossard
- Jelena Kovacevic
- Xavier Bresson
In Statistical and Nonlinear Physics
- Pierre Vandergheynst
- Pascal Frossard
- Xavier Bresson
- Nathanael Perraudin
- Michaël Defferrard
- José M. F. Moura
- Antonio Ortega
- Michael M. Bronstein
In Graph Learning
- Xavier Bresson
- Pierre Vandergheynst
- Pascal Frossard
- Nathanael Perraudin
- Michael M. Bronstein
- Michaël Defferrard
- José M. F. Moura
- Antonio Ortega
In Information Theory
Citations in the corpus
- Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (2016, background): “The works of [34, 25, 26] redefined uncertainty principles on graphs and showed that while intuitive concepts may be lost, enhanced localization principles can be derived.”
- Graph Signal Processing: Overview, Challenges, and Applications (2017, background): “Other contributions, such as [135], [136], have also explored the challenges in directly extending the concept of an uncertainty”
- Global and Local Uncertainty Principles for Signals on Graphs (2016, background): “This idea is generalized to weighted graphs in [41].”