Sparse eigenvectors of graphs

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 eigenvecto...

Full description

Saved in:
Bibliographic Details
Main Authors: Teke, Oguzhan, Vaidyanathan, P. P.
Format: Conference Proceeding
Language:English
Subjects:
Eigenvalues and eigenfunctions
Electrical engineering
Graph signals
Laplace equations
Signal processing
sparse eigenvectors
Sparse matrices
sparsity
Sufficient conditions
Uncertainty
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2379-190X
DOI:10.1109/ICASSP.2017.7952888