A Caltech Library Service

Discrete uncertainty principles on graphs

Teke, Oguzhan and Vaidyanathan, P. P. (2016) Discrete uncertainty principles on graphs. In: 50th Asilomar Conference on Signals, Systems and Computers. IEEE , Piscataway, NJ, pp. 1475-1479. ISBN 978-1-5386-3954-2.

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

Use this Persistent URL to link to this item:


This paper advances a new way to formulate the uncertainty principle for graphs, by using a non-local measure based on the notion of sparsity. The uncertainty principle is formulated based on the total number of nonzero elements in the signal and its corresponding graph Fourier transform (GFT). By providing a lower bound for this total number, it is shown that a nonzero graph signal and its GFT cannot be arbitrarily sparse simultaneously. The theoretical bound on total sparsity is derived. For several real-world graphs this bound can actually be achieved by choosing the graph signals to be appropriate eigenvectors of the graph.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Teke, Oguzhan0000-0002-1131-5206
Vaidyanathan, P. P.0000-0003-3003-7042
Additional Information:© 2016 IEEE. This work was supported in parts by the ONR grant N00014-15-1-2118, and the California Institute of Technology.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-15-1-2118
Subject Keywords:Graph signal processing, uncertainty principles, sparsity
Record Number:CaltechAUTHORS:20170308-162825251
Persistent URL:
Official Citation:O. Teke and P. P. Vaidyanathan, "Discrete uncertainty principles on graphs," 2016 50th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, 2016, pp. 1475-1479. doi: 10.1109/ACSSC.2016.7869622
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74947
Deposited By: Kristin Buxton
Deposited On:09 Mar 2017 04:41
Last Modified:15 Nov 2021 16:29

Repository Staff Only: item control page