A Caltech Library Service

Sparse eigenvectors of graphs

Teke, Oguzhan and Vaidyanathan, P. P. (2017) Sparse eigenvectors of graphs. In: 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE , Piscataway, NJ, pp. 3904-3908. ISBN 978-1-5090-4117-6 .

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


In order to analyze signals defined over graphs, many concepts from the classical signal processing theory have been extended to the graph case. One of these concepts is the uncertainty principle, which studies the concentration of a signal on a graph and its graph Fourier basis (GFB). An eigenvector of a graph is the most localized signal in the GFB by definition, whereas it may not be localized in the vertex domain. However, if the eigenvector itself is sparse, then it is concentrated in both domains simultaneously. In this regard, this paper studies the necessary and sufficient conditions for the existence of 1, 2, and 3-sparse eigenvectors of the graph Laplacian. The provided conditions are purely algebraic and only use the adjacency information of the graph. Examples of both classical and real-world graphs with sparse eigenvectors are also presented.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Teke, Oguzhan0000-0002-1131-5206
Additional Information:© 2017 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 signals, sparsity, sparse eigenvectors
Record Number:CaltechAUTHORS:20170621-170410534
Persistent URL:
Official Citation:O. Teke and P. P. Vaidyanathan, "Sparse eigenvectors of graphs," 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA, USA, 2017, pp. 3904-3908. doi: 10.1109/ICASSP.2017.7952888
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:78445
Deposited By: Kristin Buxton
Deposited On:22 Jun 2017 01:18
Last Modified:03 Oct 2019 18:08

Repository Staff Only: item control page