A Caltech Library Service

Uncertainty Principles and Sparse Eigenvectors of Graphs

Teke, Oguzhan and Vaidyanathan, P. P. (2017) Uncertainty Principles and Sparse Eigenvectors of Graphs. IEEE Transactions on Signal Processing, 65 (20). pp. 5406-5420. ISSN 1053-587X.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Teke, Oguzhan0000-0002-1131-5206
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.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-15-1-2118
Subject Keywords:Graph signals, graph Fourier basis, sparsity, uncertainty principles, sparse eigenvectors
Record Number:CaltechAUTHORS:20170725-093243393
Persistent URL:
Official Citation:O. Teke and P. P. Vaidyanathan, "Uncertainty Principles and Sparse Eigenvectors of Graphs," in IEEE Transactions on Signal Processing, vol. 65, no. 20, pp. 5406-5420, Oct.15, 15 2017. doi: 10.1109/TSP.2017.2731299
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:79325
Deposited By: Tony Diaz
Deposited On:25 Jul 2017 16:54
Last Modified:17 Aug 2017 00:05

Repository Staff Only: item control page