发帖
雷达卡
摘要翻译：
研究了为有向图（有向图）构造图Fourier变换(GFT)的问题，该变换将图信号分解成关于底层网络的不同变化模式。因此，为了捕获低、中、高频，我们寻求一个有向图(D)GFT，使得正交频率分量在图谱域中尽可能扩展。为此，我们提倡两步设计，由此我们:(i)找到候选基向量可以达到的最大有向变化（即有向图上频率的新概念）；以及(ii)在可实现的频率范围内最小化平滑频谱色散函数以获得期望的扩展DGFT基。这两个步骤都涉及非凸的正交约束优化问题，通过Stiefel流形上的可证收敛可行优化方法有效地解决了这些问题。我们还提出了一个启发式的DGFT基构造由Laplacian特征向量的无向版本的有向图。我们证明了谱色散最小化问题可以转化为在候选频率分量集合上的超模优化问题，这些候选频率分量的正交性可以通过拟阵基约束来实现。这就促使我们采用一种可扩展的贪婪算法来获得具有可量化的最坏情况谱色散的近似解。我们通过在合成网络和真实网络上的数值测试来说明我们的DGFT算法的有效性。我们还进行了一个图形信号去噪任务，其中DGFT基被用来分解和低通滤波温度记录在整个美国。
---
英文标题：
《A Directed Graph Fourier Transform with Spread Frequency Components》
---
作者：
Rasoul Shafipour, Ali Khodabakhsh, Gonzalo Mateos, Evdokia Nikolova
---
最新提交年份：
2018
---
分类信息：
一级分类：Electrical Engineering and Systems Science 电气工程与系统科学
二级分类：Signal Processing 信号处理
分类描述：Theory, algorithms, performance analysis and applications of signal and data analysis, including physical modeling, processing, detection and parameter estimation, learning, mining, retrieval, and information extraction. The term "signal" includes speech, audio, sonar, radar, geophysical, physiological, (bio-) medical, image, video, and multimodal natural and man-made signals, including communication signals and data. Topics of interest include: statistical signal processing, spectral estimation and system identification; filter design, adaptive filtering / stochastic learning; (compressive) sampling, sensing, and transform-domain methods including fast algorithms; signal processing for machine learning and machine learning for signal processing applications; in-network and graph signal processing; convex and nonconvex optimization methods for signal processing applications; radar, sonar, and sensor array beamforming and direction finding; communications signal processing; low power, multi-core and system-on-chip signal processing; sensing, communication, analysis and optimization for cyber-physical systems such as power grids and the Internet of Things.
信号和数据分析的理论、算法、性能分析和应用，包括物理建模、处理、检测和参数估计、学习、挖掘、检索和信息提取。“信号”一词包括语音、音频、声纳、雷达、地球物理、生理、（生物）医学、图像、视频和多模态自然和人为信号，包括通信信号和数据。感兴趣的主题包括：统计信号处理、谱估计和系统辨识；滤波器设计；自适应滤波/随机学习；（压缩）采样、传感和变换域方法，包括快速算法；用于机器学习的信号处理和用于信号处理应用的机器学习；网络与图形信号处理；信号处理中的凸和非凸优化方法；雷达、声纳和传感器阵列波束形成和测向；通信信号处理；低功耗、多核、片上系统信号处理；信息物理系统的传感、通信、分析和优化，如电网和物联网。
--
---
英文摘要：
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: (i) find the maximum directed variation (i.e., a novel notion of frequency on a digraph) a candidate basis vector can attain; and (ii) 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 provably convergent, feasible optimization method on the Stiefel manifold. We also propose a heuristic to construct the DGFT basis from Laplacian eigen-vectors 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.
---
PDF链接：
https://arxiv.org/pdf/1804.03
京公网安备 11010802022788号
