离散傅里叶变换到图傅里叶变换的一致数学框架

A Unified Mathematical Framework from the Discrete Fourier Transform to the Graph Fourier Transform

摘要: 离散傅里叶变换与图傅里叶变换之间的联系已在图信号处理相关研究中得到广泛讨论，但相关结果通常分散于傅里叶分析、谱图理论与图信号处理文献之中，面向教学和跨领域研究的系统性、一体化推导仍有进一步梳理的必要。针对这一问题，本文从离散傅里叶变换出发，在已有图信号处理理论的基础上构建由规则离散信号域向一般无向图域推广的数学分析框架。首先，在环形图模型下考察邻接矩阵与图拉普拉斯矩阵的谱结构，分析离散傅里叶基与图谱基之间的对应关系，说明离散傅里叶变换可视为特定图结构上的图傅里叶变换。其次，引入图移位算子作为刻画图拓扑作用于图信号的基本线性算子，给出图移位算子视角下的图傅里叶变换。进一步地，本文从图拉普拉斯二次型出发，系统阐释其与相邻节点信号差异、图信号平滑度以及低频/高频图模态之间的关系，从而为“图频率”提供更明确的物理和几何解释。本文的贡献不在于提出全新的GFT定义，而在于对DFT到GFT这一已知理论联系给出系统性、教学性和一体化的数学梳理，为理解经典傅里叶分析与图信号谱分析之间的连续关系提供更清晰的推导路径。

Abstract: The relationship between the discrete Fourier transform (DFT) and the graph Fourier transform (GFT) has been widely investigated in graph signal processing. Nevertheless, relevant theoretical results remain scattered across the literature on Fourier analysis, spectral graph theory, and graph signal processing, and a unified, pedagogically oriented derivation for teaching and interdisciplinary research is still lacking. To bridge this gap, this paper takes the DFT as its starting point and, building upon existing graph signal processing theories, constructs a mathematical analysis framework that extends from regular discrete signal domains to general undirected graph domains. First, under cycle graphs, we investigate the spectral properties of the adjacency matrix and the graph Laplacian, analyze the correspondence between the discrete Fourier basis and the graph spectral basis, and demonstrate that the DFT serves as a special instance of the GFT defined on cycle graphs. Second, we introduce the graph shift operator as the fundamental linear operator characterizing the action of graph topology on graph signals, and derive the GFT from this operator perspective. Moreover, starting from the quadratic form of the graph Laplacian, we systematically elaborate on its inherent connections with inter-node signal differences, graph signal smoothness, and low-/high-frequency graph modes, thereby offering more explicit physical and geometric interpretations of graph frequency. Accordingly, the core contribution of this paper is not a novel definition of the GFT, but rather a systematic and pedagogical mathematical exposition of the established theoretical link from the DFT to the GFT, providing a clearer derivation route for understanding the theoretical continuity between classical Fourier analysis and graph spectral signal analysis.