Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 15, 2017 | public
Journal Article

Uncertainty Principles and Sparse Eigenvectors of Graphs

Abstract

Analysis of signals defined over graphs has been of interest in the recent years. In this regard, many concepts from the classical signal processing theory have been extended to the graph case, including uncertainty principles that study the concentration of a signal on a graph and in its graph Fourier basis (GFB). This paper advances a new way to formulate the uncertainty principle for signals defined over graphs, by using a nonlocal measure based on the notion of sparsity. To be specific, the total number of nonzero elements of a graph signal and its corresponding graph Fourier transform (GFT) is considered. A theoretical lower bound for this total number is derived, and it is shown that a nonzero graph signal and its GFT cannot be arbitrarily sparse simultaneously. When the graph has repeated eigenvalues, the GFB is not unique. Since the derived lower bound depends on the selected GFB, a method that constructs a GFB with the minimal uncertainty bound is provided. In order to find signals that achieve the derived lower bound (i.e., the most compact on the graph and in the GFB), sparse eigenvectors of the graph are investigated. It is shown that a connected graph has a 2-sparse eigenvector (of the graph Laplacian) when there exist two nodes with the same neighbors. In this case, the uncertainty bound is very low, tight, and independent of the global structure of the graph. For several examples of classical and real-world graphs, it is shown that 2-sparse eigenvectors, in fact, exist.

Additional Information

© 2015 IEEE. Manuscript received August 2, 2016; revised January 18, 2017, May 22, 2017, and July 8, 2017; accepted July 13, 2017. Date of publication July 24, 2017; date of current version August 10, 2017. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Pierre Borgnat. This work was supported in part by the NSF under Grant CCF-1712633, in part by the ONR Grant N00014-15-1-2118, and in part by the Electrical Engineering Carver Mead Research Seed Fund of the California Institute of Technology. The authors wish to thank the anonymous reviewers for pointing out the study in [19], for thoughtful questions about random graphs and for other very useful suggestions.

Additional details

Created:
August 19, 2023
Modified:
October 26, 2023