有向图的谐波分析：从傅里叶到小波

Harmonic Analysis of Digraphs: From Fourier to Wavelet

摘要: 数据化时代中，高效地分析和处理数据引起了研究者的广泛关注。利用图模型建立数据的结构，进而对数据进行分析处理，发展起了图信号处理。最初是在无向图中发展的，图拉普拉斯在其中发挥着重要作用。神经科学、社会网络等领域的数据网络都是定向的，从而信号处理需要扩展到有向图中。在有向图中，图拉普拉斯不再使用，将参考算子换作图上的游走算子。进而把随机游走算子的特征向量集作为有向图上函数的非正交傅里叶型基。从随机游动算子的狄利克雷能量获得的特征向量的变化与相关特征值的实部联系起来，找到了频率解释。在有向图中，又分别回顾了小波变换和抽取小波变换作为谱图小波和扩散小波框架的扩展。上述都是在算子是可以对角化的前提下提出的。但是现实生活中的数据模型不会只局限于对角化的算子，因此本文将算子扩展到了整数项的扩张矩阵中，从而提出了有向图上的紧支撑帕塞瓦尔小波框架及其多分辨率分析，并且也找到了基于这类矩阵下的频率解释。此类小波框架不仅在构造时简单高效，而且在性质上也有很大优势：有确定的消失矩的阶数，使尽量多的小波系数为零或者产生尽量少的非零小波系数，利于消除噪声。

Abstract: In the age of data, the efficient analysis and processing of data have attracted the wide attention of researchers. The graph model is used to establish the structure of the data, and then the data is analyzed and processed, and the graph signal processing is developed. It was originally developed in undirected graphs, in which the Laplacian operator on the graph plays an important role. Since data networks in areas such as neuroscience and social networks are oriented, signal processing needs to be extended to directed graphs. In the case of digraphs, the reference operator is replaced by the wandering operator on the graph. Then the eigenvector set of the random walk operator is taken as the non-orthogonal Fourier basis of the function on the digraph. The variation of the eigenvector obtained from the Dirichlet energy of the random walk operator is associated with the real part of the relevant eigenvalue, and the frequency interpretation is found. In the directed graph, the wavelet transform and the extraction wavelet transform are reviewed respectively as extensions of spectral wavelet and diffusion wavelet frames. All of the above are proposed under the premise that the operator can be diagonalized. However, the data model in real life is not limited to diagonalized operators, so this paper extends the operators to the extended matrix of integer terms, thereby proposing the compact-supported Parseval wavelet framework on the directed graph and its multi-resolution analysis, and also finding the frequency interpretation based on such matrices. This kind of wavelet frame is not only simple and efficient in construction, but also has great advantages in nature: There is a definite order of vanishing moment, so that as many wavelet coefficients as possible are zero or as few non-zero wavelet coefficients as possible, which is conducive to noise elimination.