A Directed Graph Fourier Transform With Spread Frequency Components
A Directed Graph Fourier Transform With Spread Frequency Components
复制标题
DOI：
10.1109/tsp.2018.2886151
复制
发表时间：
2018-04
影响因子：
5.4
通讯作者：
Rasoul Shafipour;Ali Khodabakhsh;G. Mateos;E. Nikolova
中科院分区：
文献类型：
--
作者：
Rasoul Shafipour;Ali Khodabakhsh;G. Mateos;E. Nikolova
我们研究的问题，构建一个图形傅立叶变换（GFT）的有向图（有向图），它分解成不同的模式的变化相对于底层网络的图形信号。因此，为了捕获低、中和高频率，我们寻求有向图（D）GFT，使得标准正交频率分量在图形谱域中尽可能地扩展。为此，我们提倡两步设计，其中我们1）找到最大定向变异（即，有向图上的频率的新概念）候选基向量可以获得，以及2）在可获得的频率范围上最小化平滑频谱色散函数以获得期望的扩展DGFT基。这两个步骤涉及非凸，正交约束的优化问题，这是有效地解决了通过一个可行的优化方法的Stiefel流形，证明收敛到一个固定的解决方案。我们还提出了一个启发式构造DGFT基础的拉普拉斯特征向量的无向版本的有向图。我们表明，频谱色散最小化问题可以被铸造为超模优化的候选频率分量，其正交性可以通过一个拟阵基约束。这促使采用可扩展的贪婪算法来获得具有可量化的最坏情况频谱色散的近似解。我们说明了我们的DGFT算法的有效性，通过数值试验合成和现实世界的网络。我们还进行了图形信号去噪任务，其中DGFT基础用于分解，然后低通滤波器在美国各地记录的温度。
We study the problem of constructing a graph Fourier transform (GFT) for directed graphs (digraphs), which decomposes graph signals into different modes of variation with respect to the underlying network. Accordingly, to capture low, medium, and high frequencies we seek a digraph (D)GFT such that the orthonormal frequency components are as spread as possible in the graph spectral domain. To that end, we advocate a two-step design whereby we 1) find the maximum directed variation (i.e., a novel notion of frequency on a digraph) a candidate basis vector can attain and 2) minimize a smooth spectral dispersion function over the achievable frequency range to obtain the desired spread DGFT basis. Both steps involve non-convex, orthonormality-constrained optimization problems, which are efficiently tackled via a feasible optimization method on the Stiefel manifold that provably converges to a stationary solution. We also propose a heuristic to construct the DGFT basis from Laplacian eigenvectors of an undirected version of the digraph. We show that the spectral-dispersion minimization problem can be cast as supermodular optimization over the set of candidate frequency components, whose orthonormality can be enforced via a matroid basis constraint. This motivates adopting a scalable greedy algorithm to obtain an approximate solution with quantifiable worst-case spectral dispersion. We illustrate the effectiveness of our DGFT algorithms through numerical tests on synthetic and real-world networks. We also carry out a graph-signal denoising task, whereby the DGFT basis is used to decompose and then low pass filter temperatures recorded across the United States.