On Graph Uncertainty Principle and Eigenvector Delocalization

Elizaveta Rebrova; Palina Salanevich

doi:10.1109/SampTA59647.2023.10301367

On Graph Uncertainty Principle and Eigenvector Delocalization

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Uncertainty principles present an important theoretical tool in signal processing, as they provide limits on the time-frequency concentration of a signal. In many real-world applications the signal domain has a complicated irregular structure that can be described by a graph. In this paper, we focus on the global uncertainty principle on graphs and propose new connections between the uncertainty bound for graph signals and graph eigenvectors delocalization. We also derive uncertainty bounds for random d-regular graphs and provide numerically efficient upper and lower approximations for the uncertainty bound on an arbitrary graph.

Original language	English (US)
Title of host publication	2023 International Conference on Sampling Theory and Applications, SampTA 2023
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9798350328851
DOIs	https://doi.org/10.1109/SampTA59647.2023.10301367
State	Published - 2023
Externally published	Yes
Event	2023 International Conference on Sampling Theory and Applications, SampTA 2023 - New Haven, United States Duration: Jul 10 2023 → Jul 14 2023

Publication series

Name	2023 International Conference on Sampling Theory and Applications, SampTA 2023

Conference

Conference	2023 International Conference on Sampling Theory and Applications, SampTA 2023
Country/Territory	United States
City	New Haven
Period	7/10/23 → 7/14/23

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Statistics and Probability
Artificial Intelligence
Computational Theory and Mathematics
Computer Science Applications
Signal Processing

Access to Document

10.1109/SampTA59647.2023.10301367

Cite this

Rebrova, E., & Salanevich, P. (2023). On Graph Uncertainty Principle and Eigenvector Delocalization. In 2023 International Conference on Sampling Theory and Applications, SampTA 2023 (2023 International Conference on Sampling Theory and Applications, SampTA 2023). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SampTA59647.2023.10301367

@inproceedings{37179b6272ab4d07adfd7e6dc39307c4,

title = "On Graph Uncertainty Principle and Eigenvector Delocalization",

abstract = "Uncertainty principles present an important theoretical tool in signal processing, as they provide limits on the time-frequency concentration of a signal. In many real-world applications the signal domain has a complicated irregular structure that can be described by a graph. In this paper, we focus on the global uncertainty principle on graphs and propose new connections between the uncertainty bound for graph signals and graph eigenvectors delocalization. We also derive uncertainty bounds for random d-regular graphs and provide numerically efficient upper and lower approximations for the uncertainty bound on an arbitrary graph.",

author = "Elizaveta Rebrova and Palina Salanevich",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 International Conference on Sampling Theory and Applications, SampTA 2023 ; Conference date: 10-07-2023 Through 14-07-2023",

year = "2023",

doi = "10.1109/SampTA59647.2023.10301367",

language = "English (US)",

series = "2023 International Conference on Sampling Theory and Applications, SampTA 2023",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2023 International Conference on Sampling Theory and Applications, SampTA 2023",

address = "United States",

}

Rebrova, E & Salanevich, P 2023, On Graph Uncertainty Principle and Eigenvector Delocalization. in 2023 International Conference on Sampling Theory and Applications, SampTA 2023. 2023 International Conference on Sampling Theory and Applications, SampTA 2023, Institute of Electrical and Electronics Engineers Inc., 2023 International Conference on Sampling Theory and Applications, SampTA 2023, New Haven, United States, 7/10/23. https://doi.org/10.1109/SampTA59647.2023.10301367

On Graph Uncertainty Principle and Eigenvector Delocalization. / Rebrova, Elizaveta; Salanevich, Palina.
2023 International Conference on Sampling Theory and Applications, SampTA 2023. Institute of Electrical and Electronics Engineers Inc., 2023. (2023 International Conference on Sampling Theory and Applications, SampTA 2023).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On Graph Uncertainty Principle and Eigenvector Delocalization

AU - Rebrova, Elizaveta

AU - Salanevich, Palina

PY - 2023

Y1 - 2023

N2 - Uncertainty principles present an important theoretical tool in signal processing, as they provide limits on the time-frequency concentration of a signal. In many real-world applications the signal domain has a complicated irregular structure that can be described by a graph. In this paper, we focus on the global uncertainty principle on graphs and propose new connections between the uncertainty bound for graph signals and graph eigenvectors delocalization. We also derive uncertainty bounds for random d-regular graphs and provide numerically efficient upper and lower approximations for the uncertainty bound on an arbitrary graph.

AB - Uncertainty principles present an important theoretical tool in signal processing, as they provide limits on the time-frequency concentration of a signal. In many real-world applications the signal domain has a complicated irregular structure that can be described by a graph. In this paper, we focus on the global uncertainty principle on graphs and propose new connections between the uncertainty bound for graph signals and graph eigenvectors delocalization. We also derive uncertainty bounds for random d-regular graphs and provide numerically efficient upper and lower approximations for the uncertainty bound on an arbitrary graph.

UR - http://www.scopus.com/inward/record.url?scp=85178509915&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85178509915&partnerID=8YFLogxK

U2 - 10.1109/SampTA59647.2023.10301367

DO - 10.1109/SampTA59647.2023.10301367

M3 - Conference contribution

AN - SCOPUS:85178509915

T3 - 2023 International Conference on Sampling Theory and Applications, SampTA 2023

BT - 2023 International Conference on Sampling Theory and Applications, SampTA 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2023 International Conference on Sampling Theory and Applications, SampTA 2023

Y2 - 10 July 2023 through 14 July 2023

ER -

On Graph Uncertainty Principle and Eigenvector Delocalization

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this