Uncertainty Principles and Sparse Eigenvectors of Graphs
Uncertainty Principles and Sparse Eigenvectors of Graphs
复制标题
DOI：
10.1109/tsp.2017.2731299
复制
发表时间：
2017-10-15
影响因子：
5.4
通讯作者：
Vaidyanathan, P. P.
中科院分区：
文献类型：
--
作者：
Teke, Oguzhan;Vaidyanathan, P. P.
定义在图上的信号的分析近年来一直是人们感兴趣的。在这方面，经典信号处理理论中的许多概念已扩展到图形情况，包括研究信号在图形及其图形傅里叶基（GFB）中的集中度的不确定性原理。本文提出了一种新的方法来制定的不确定性原则的信号定义在图上，通过使用非局部测量的概念的基础上稀疏。具体而言，考虑图形信号的非零元素的总数及其对应的图形傅立叶变换（GFT）。这个总数的理论下限推导，它表明，一个非零的图形信号和GFT不能任意稀疏的同时。当图具有重复特征值时，GFB不是唯一的。由于推导出的下界依赖于所选择的GFB，一种方法，构建一个GFB与最小的不确定性界。为了找到达到导出的下限（即，例如，图的稀疏特征向量。证明了当存在两个具有相同邻居的节点时，连通图具有2-稀疏特征向量（图拉普拉斯算子的）。在这种情况下，不确定性边界非常低，紧，并且与图的全局结构无关。对于经典和现实世界的图的几个例子，它表明，2-稀疏特征向量，事实上，存在。
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., themost 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.