On Graph Uncertainty Principle and Eigenvector Delocalization

Elizaveta Rebrova, Palina Salanevich

Research output: Working paperPreprintAcademic

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 languageEnglish
PublisherarXiv
DOIs
Publication statusPublished - 27 Jun 2023

Keywords

  • cs.IT
  • math.IT
  • math.OC
  • math.PR

Fingerprint

Dive into the research topics of 'On Graph Uncertainty Principle and Eigenvector Delocalization'. Together they form a unique fingerprint.

Cite this