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

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.

1. 引言

数据无处不在且数量巨大，处于一个社会数据以指数级速度积累的世界里，管理、利用和分析这些数据网络已经成为这个时代的挑战之一。从个人基因或身体监测数据到社交网络、流量营销模式以及交通网络等，无一不记录在册。这种网络数据和它们之间复杂性交互可以模型化为复杂的有节点和边的图结构，都表现出高维空间中的图形结构生活。

因此，为了分析和理解这些图形数据，有必要创建有效的数学和计算方法来处理和分析这些图形和图形上的数据。在节点上添加属性，并将其建模为图上的信号。

在现有的方法中，大量涉及(图)拉普拉斯函数 [1] [2] [3] [4] [5] ：1) 作为数学和物理的一门基础学科，拉普拉斯算子通过对其谱的研究，从流形 [6] 或图 [7] 中提取相关的几何性质，并在谱聚类 [5] 和半监督学习 [8] 等机器学习应用中发挥作用。2) 在连续空间中，Laplace-Beltrami算子的特征函数代表了流形上傅里叶基的推广 [6] [9] 。3) 在离散空间中，当无向图被认为是流形的离散化或抽样时，图拉普拉斯的特征向量形成无向图上函数的标准正交傅里叶型基 [1] [10] ，然后，与每个特征向量相关联的特征值和频率的概念相关 [10] 。

由于这些性质，图拉普拉斯通过“图上的信号处理”这一数学框架架起了谱图理论和信号处理之间的桥梁 [1] [10] 。该框架旨在扩展经典信号处理的概念，如滤波或采样，用于定义在图的顶点上的函数。所有这些重要的结构都被独特地设计在无向图上。

因此，图上的信号处理首先是在无向图的背景下发展起来的，它将图拉普拉斯(组合或归一化) [7] 作为其核心元素。图拉普拉斯算子是一个对称的正半定算子。根据谱定理，图拉普拉斯允许一个特征向量的标准正交基，这些特征向量可以被认为是傅里叶模，相应的特征值与频率的概念相关联。

有向图广泛出现在各种现实世界的应用中，从社交网络到计算生物学，其中边缘的方向性带来了有用的信息。信号处理在有向图上的扩展引起了人们的兴趣。因此需要将图上的信号处理框架扩展到有向图的情况。有向图是图论中的一个基本概念，由一组节点和一组有向边组成，用于描述节点之间的关系。有向图的广泛应用主要是基于有向图的连通性、稳定性、聚类性以及中心性等。为了更好地将有向图的图像特征显示出来，引入了有向图的谐波分析，为相关领域的研究和应用提供了新的方向。本章的目的是对图上的信号处理框架扩展到有向图的情况提供一些答案。

首先在有向图上可以直接使用拉普拉斯算子吗？形式上，直接使用图信号处理的核心元素，即图拉普拉斯，已经不再合适。有向图通常由非对称邻接矩阵表示。在有向图的情况下，总是可以定义一个图拉普拉斯算子，但是在无向图中拉普拉斯算子相关的谱性质(例如非负实特征值和标准正交特征基的存在)，在有向图的情况下没有得到验证。对于特征向量的变化与频率的概念相联系的有向图的拉普拉斯函数的定义，没有简单的共识。因此，在有向图上的信号处理和首要挑战就是：在无向图上推广的基于拉普拉斯的傅里叶分析应该建立在有向图中哪些参考算子的基础上？

随后，在 [11] [12] [13] 中，将图上随机游走算子作为扩展有向图上信号处理框架的合适参考算子。像图拉普拉斯算子一样，随机游走算子与扩散的概念有关。然而，与图拉普拉斯函数不同的是，它的定义在有向图和无向图上都是直接的。假设随机游走算子是可对角化的，它可能允许复共轭特征向量以及相关的复共轭特征值。此框架是基于这样一个事实：随机游走算子的特征向量通过其相关的狄利克雷能量 [14] 的变分分析与特征值的实部相关。因此，有向图上随机游走算子的给定特征向量的狄利克雷能量可以视为有向图的频率，使用与 [10] 相同的类比，现在用于有向图。有了这个频率的概念，随机游走算子的特征向量在有向图上形成一个合适的傅里叶基。

接着考虑随机游走算子作为参考算子，其相关的特征向量作为有向图上定义的函数的傅里叶基，对有向图的谐波分析的最后一部分包括为在有向图的顶点上定义的函数构建多分辨率分析。无论是有向图还是无向图，都具有不同尺度的结构。由于传统信号处理中多分辨率小波分析的高效性和图数据的多尺度性，近年来出现了许多多分辨率图构建。在这里，提出了一种围绕随机游走算子构建的谐波分析，其多分辨率结构将谱图小波 [14] [15] 和扩散小波 [4] [16] 推广到有向图上。

很多研究都是基于可对角化的算子，但是实际生活中数据网络不局限于此。从而本文将把算子从可对角化扩大到整数项的扩张矩阵中，可以更加利于现实数据分析和处理。并且基于此提出的紧支撑帕塞瓦尔小波框架不仅在构造时简单高效，而且在性质上和应用中也有很大优势：有确定的消失矩的阶数，使尽量多的小波系数为零或者产生尽量少的非零小波系数，利于消除噪声。

本文其余部分结构安排如下：在第二节中，介绍了图论的基本方面，并回顾图信号处理的基础。在第三节中，给出了由随机游走算子构建的有向图上的算子及其性质，并回顾了一类有向图上的算子，表示为随机游走算子与其时间反转算子之间的凸组合。第四节将有向图上的傅里叶变换表示为随机游走算子的特征向量集，通过研究随机游走特征向量的变化，回顾了在有向图上定义的函数的傅里叶型分析。第五节致力于有向图的多分辨率分析。介绍了冗余小波结构，以及一种以随机游走算子作为参考算子的临界采样小波结构。在第六节中，将研究算子从对角化矩阵扩大为整数项的扩张矩阵，再此基础上提出了紧支撑帕塞瓦尔小波框架，并给出了相应的频率解释，随后基于多分辨分析提出了低通、高通滤波器。在第七节中，给出了结论。

2. 准备工作

2.1. 图像信号处理基础

图上的信号处理是一个数学框架，其中谐波分析的核心概念被推广到图的顶点上定义的函数。在本节中，介绍了图框架上信号处理的基本方面，并给出了一些补充说明。

2.1.1. 图论基础

设 $\varsigma =\left(\nu ,\epsilon ,\omega \right)$ 是一个加权有向图，其中 $\nu =\left\{{\nu }_1,\cdots ,{\nu }_N\right\}$ 是有限的顶点集， $\epsilon \subseteq \nu \times \nu$ 是一组有向边。每个边 $e_{ij}=\left({\nu }_i,{\nu }_j\right)$ 是有向的，并且表示从顶点 ${\nu }_i$ 到 ${\nu }_j$ 的连接。加权函数 $\omega :\nu \times \nu \to {ℝ}_{+}$ 将非负实值与顶点相对应：当 $e_{ij}\in \epsilon$ 时， $\omega \left({\nu }_i,{\nu }_j\right)>0$ ，其他情形下 $\omega \left({\nu }_i,{\nu }_j\right)=0$ 。 $\left|\nu \right|=N$ 表示顶点集合 $\nu$ 的基数，即 $\nu$ 中的顶点的总数。一个加权图可以由其加权邻接矩阵 $W={\left\{{\omega }_{ij}\right\}}_{1\le i,j\le N}\in {ℝ}_{+}^{N\times N}$ 来表示，其中 ${\omega }_{ij}=\omega \left({\nu }_i,{\nu }_j\right)$ 是各边 $e_{ij}$ 相关的权重。定义顶点 ${\nu }_i\in \nu$ 的出度和入度分别为 $d_i^{+}={\displaystyle \underset{j=1}{\overset{N}{\sum }}{\omega }_{ij}}$ 和 $d_i^{-}={\displaystyle \underset{j=1}{\overset{N}{\sum }}{\omega }_{ji}}$ 。如果图的每队顶点之间在每个方向上都有一条路径，则称有向图为强连通有向图 [17] 。

仅适用于非负权重的加权有向图的情况，限制是 $W={\left\{{\omega }_{ij}\right\}}_{1\le i,j\le N}\in {ℝ}_{+}^{N\times N}$ 。

2.1.2. 图信号

设 $f:\nu \to ℂ$ 是给定有向图 $\varsigma$ 的顶点集合 $\nu$ 上定义的函数。将图信号f应用于每个节点 ${\nu }_i\in \nu$ 的列向量表示，即 $f={\left[f\left({\nu }_1\right),\cdots ,f\left({\nu }_N\right)\right]}^{\text{T}}\in {ℂ}^N$ 。

在本文中，假设图信号定义在 ${\mathcal{l}}^2\left(\nu ,\nu \right)$ 中，在 $\varsigma$ 的顶点集合 $\nu$ 上定义的函数是在希尔波特空间上。 $\varsigma$ 的顶点集 $\nu$ 被赋予了与 $\nu$ 相关的内积， $\nu$ 是一个正的任意顶点度量。定义内积为 ${\langle f,g\rangle }_{\nu }={\displaystyle \underset{x\in \nu }{\sum }\overline{f\left(x\right)}g\left(x\right)\nu }\left(x\right),\forall f,g$ ，其中 $\overline{f\left(x\right)}$ 表示 $f\left(x\right)$ 的复共轭。

2.2. 图上的线性滤波器

图上的线性算子由矩阵 $H\in {ℂ}^{N\times N}$ 来表示，作用于图信号输入 $s\in {ℂ}^N$ 根据矩阵的向量积 $\tilde{s}=Hs$ 并产生图信号输出 $\tilde{s}\in {ℂ}^N$ 。

在图信号处理的框架内，受传统信号处理的启发，主要对图滤波器感兴趣。由于它可以与所选择的参考算子R进行交换，图滤波器被认为是线性的和“移位不变的”(即LSI)。邻接矩阵被选择为参考算子，并且现在已经讨论了其他选择是可能的(例如 [14] )。因此，考虑图上的任何参考算子R。

定义2.1 图滤波器是具有矩阵表示H的线性移不变算子，因此它可以与所选算子R进行转换，即 $HR=RH$ 。

定理2.1 令R是有向图 $\varsigma$ 上的参考算子，假设R的特征向量与最小多项式相等，即 $p_R\left(x\right)=m_R\left(x\right)$ ，那么，图滤波器H是线性移不变的，当且仅当H被表示为R的多项式 $H={\displaystyle \underset{t=0}{\overset{T}{\sum }}{h}_t{R}^t},h_t\in ℂ,\forall t=0,\cdots ,T$ 。

3. 有向图上的正则算子

介绍了基本算子及其性质，以便对有向图进行分析。给出了由随机游走算子构建的有向图上的算子及其性质，回顾了一类有向图上的算子，其表示为随机游走算子与其时间反转算子之间的凸组合。

3.1. 图上的随机游动算子

定义3.1 强连通有向图 $\varsigma =\left(\nu ,\epsilon ,\omega \right)$ 上的随机游动是齐次马氏链 $\aleph ={\left(X_n\right)}_{n\ge 0}$ ，其具有有限状态空间并且转移概率与边的权重成比例。转换矩阵P中的元素可以写成 $p\left(x,y\right),\forall x,y\in \nu$ ，定义为

$p\left(x,y\right)={\rm P}\left(X_{n+1}=y|X_n=x\right)=\frac{\omega \left(x,y\right)}{{\displaystyle {\sum }_y\omega \left(x,y\right)}}$ 。

从图论的角度来看，转移矩阵 $P\in {ℝ}^{N\times N}$ 等于 $P=D^{-1}W$ ，其中 $D=diag\left\{d_1,\cdots ,d_n\right\}$ 是顶点的出度对角矩阵。W是加权邻接矩阵， $P^n$ 称为n步转移矩阵，写为 $p^n\left(x,y\right),\forall x,y\in \nu$ ，定义为 $p^n\left(x,y\right)={\rm P}\left(X_n=y|X_0=x\right)$ 。

定义3.2 如果对任意 $x,y\in \nu$ ，从x到y的概率严格为正，则随机游走算子是不可约的，即 $\forall x,y\in \nu ,\exists m<\infty :{\rm P}\left(X_{n+m}=y|X_n=x\right)>0$ 。

不可约性等价于强连通性，即存在从任意顶点到任意顶点的有向路径。

定义3.3 令 $\aleph ={\left(X_n\right)}_{n\ge 0}$ 是 $\varsigma$ 上的随机游走，定义 $x\in \nu$ 返回状态为 $T_i=inf\left\{n\ge 1,X_n=i\right\}$ 。若 ${\rm P}\left(T_i|X_0=i\right)=1$ ，则顶点称为递归顶点，否则为瞬时顶点。

命题3.1 具有有限状态的不可随机游走 $\aleph$ 是正循环的。因此，随机游走 $\aleph$ 承认一个唯一的平稳分布。

在图上定义随机游走的周期性如下：

定义3.4 设 $\aleph$ 是 $\varsigma$ 上的随机游走，顶点 $x\in \nu$ 的周期为： $\sigma \left(x\right)=\gcd \left\{n\in {\mathbb{N}}^{+}:p^{\left(n\right)}\left(x,x\right)>0\right\}$ 。

定义3.5 设 $\aleph$ 是 $\varsigma$ 上的随机游走。若 $\aleph$ 是不可约的和非周期的，则随机游走 $\aleph$ 是遍历的。

给定 $\varsigma$ 上遍历游走的定态分布。

命题3.2 设 $\varsigma$ 为具有无限状态空间 $\nu$ 的有向图。如果随机游走 $\aleph$ 及其过渡矩阵P是遍历的，即不可约且非周期的。当 $n\to \infty$ 时，测度 $P^n\left(x,.\right)$ 收敛于行向量 $\pi =\left[\pi \left({\nu }_1\right),\cdots ,\pi \left({\nu }_N\right)\right]\in {ℝ}_{+}^N$ ，即具有唯一的稳定分布。特别地， $\pi P=\pi$ ，有 ${\displaystyle \underset{i=1}{\overset{N}{\sum }}\pi \left({\nu }_i\right)}=1$ ， $\pi \left({\nu }_i\right)\ge 0$ 。

3.2. 随机游走泛化

给定具有转移矩阵P的有向图 $\varsigma$ 上随机游走 $\aleph$ ，基于P构建具有各种目的的新类型的随机游走。

3.2.1. 慵懒随机游走

基于P的与慵懒随机游走 $\aleph$ 相关的转移矩阵 $\widetilde{{\rm P}}$ 表示为 $\widetilde{{\rm P}}=\frac{{\rm I}+{\rm P}}{2}$ 。慵懒随机游走 $\tilde{\aleph }$ 总是非周期的，因此，当 $\varsigma$ 强连通时， $\tilde{\aleph }$ 具有稳定测度 $\pi$ 满足 $\pi =\pi \widetilde{{\rm P}}=\pi {\rm P}$ 。

更一般地，定义 $\tilde{P}$ ，与广义惰性随机游走相关的一类转移矩阵， $\tilde{P}=\left\{{\widetilde{{\rm P}}}_{\gamma }:{\widetilde{{\rm P}}}_{\gamma }=\left(1-\gamma \right){\rm P}+\gamma {\rm I}|\gamma \in \left[0,1\right)\right\}$ 。注意到 ${\widetilde{{\rm P}}}_{\gamma }\in \tilde{P}$ 与P共享相同的特征空间。因此， $\widetilde{{\rm P}}$ 的图滤波器也是P的图滤波器。

3.2.2. 可加可逆性

由一个不可逆的遍历随机游走 $\aleph$ ，具有转移矩阵P和唯一的平稳测度 $\pi$ ，可以构造 $\aleph$ 的可加可逆性，用 $\bar{\aleph }$ 来表示。其转移矩阵是P与时间反转 ${{\rm P}}^{*}$ 之间的平均值为 $\overline{{\rm P}}=\frac{{\rm P}+{{\rm P}}^{*}}{2}$ 。 $\bar{\aleph }$ 具有相同的唯一平稳分布的可逆随机游走 $\pi$ 。

更一般地，定义 $\overline{{\rm P}}$ 为随机游走矩阵P与时间反转版本 ${{\rm P}}^{*}$ 之间的凸组合： $\bar{P}=\left\{{\overline{{\rm P}}}_{\alpha }:{\overline{{\rm P}}}_{\alpha }=\left(1-\alpha \right){\rm P}+\alpha {{\rm P}}^{*}|\alpha \in \left[0,1\right]\right\}$ ，注意到 ${\overline{{\rm P}}}_{\alpha }\in P$ 具有相同的平稳分布 $\pi$ ，但不具有相同的特征空间。

3.3. 有向图的拉普拉斯式

介绍了从无向图上扩展到有向图上的拉普拉斯算子的几个定义。

3.3.1. 归一化有向图拉普拉斯

有向图上的归一化拉普拉斯式用遍历游走在上的转换矩阵来表示，定义如下。

定义3.6 设 $\varsigma =\left(\nu ,\epsilon \right)$ 是 $\left|\nu \right|=N$ 的有向图，设 $\aleph$ 是 $\varsigma$ 上的遍历随机游走，具有过渡矩阵P和唯一平稳分布 $\pi$ 。 $\varsigma$ 上的归一化拉普拉斯定义为 $\tau ={\rm I}-\frac{{\prod }^{1/2}{\rm P}{\prod }^{-1/2}+{\prod }^{-1/2}{{\rm P}}^{{\rm T}}{\prod }^{1/2}}{2}$ ，其中I为单位矩阵， $\prod =diag\left\{\pi \left({\nu }_1\right),\cdots ,\pi \left({\nu }_N\right)\right\}$ 是平稳分布的对角矩阵。

3.3.2. 拉普拉斯随机游走

随机游走拉普拉斯 $L_{RW}$ ，定义为 $L_{RW}={\rm I}-\overline{{\rm P}}$ 。

有向图 $\tau$ 上的归一化拉普拉斯算子通过以下关系与随机游走拉普拉斯算子连接， $\tau ={\prod }^{1/2}{L}_{RW}{\prod }^{-1/2}$ 。更一般地，定义与转换矩阵 ${\overline{{\rm P}}}_{\alpha }\in \bar{P}$ 相关的有向图上的随机游走拉普拉斯数为 $L_{RW,\alpha }={\rm I}-\frac{{\overline{{\rm P}}}_{\alpha }+{\overline{{\rm P}}}_{\alpha }^{*}}{2}$ 。命题3.3 对于任意的 ${\overline{{\rm P}}}_{\alpha }\in \bar{P}$ ，有 $L_{RW,\alpha }=L_{RW},\forall \alpha \in \left[0,1\right]$ 。

3.3.3. 组合的拉普拉斯算子

引入组合拉普拉斯算子L，定义为 $L=\prod -\frac{\prod {\rm P}+{{\rm P}}^{{\rm T}}\prod }{2}$ ，后者与拉普拉斯遍历的随机游走有关， $L=\prod L_{RW}$ 。

无向图上随机游动的转移矩阵等于其时间反转马尔可夫链的转移矩阵。此外，平稳分布 $\pi$ 允许闭形式。因此，定义方程 $\tau ={\rm I}-\frac{{\prod }^{1/2}{\rm P}{\prod }^{-1/2}+{\prod }^{-1/2}{{\rm P}}^{{\rm T}}{\prod }^{1/2}}{2}$ 和 $L_{RW}={\rm I}-\overline{{\rm P}}$ 推广了无向图的常用定义 [11] 。有向图 $L=\prod -\frac{\prod {\rm P}+{{\rm P}}^{{\rm T}}\prod }{2}$ 上的组合拉普拉斯算子(此后表示为 $L_{directed}$ )将无向图上的拉普拉斯算子推广到乘法因子： $L_{undirected}=D-W=\left({\displaystyle {\sum }_i{d}_i}\right)L_{directed}$ 。

4. 有向图上的傅里叶分析

在本节中，回顾了有向图上傅里叶分析方法。这是基于随机游走算子特征向量变化的研究。将有向图上的傅里叶变换表示为随机游走算子的特征向量集，通过研究随机游走特征向量的变化，提出了对有向图上定义的函数的傅里叶型分析。

4.1. 有向图上的傅里叶变换

设P为遍历游走 $\aleph$ 的转移矩阵。假设P是可对角化的，即P允许特征值分解 ${\rm P}=\Xi \Theta {\Xi }^{-1}$ ，其中 $\Xi =\left[{\xi }_1,\cdots ,{\xi }_N\right]$ ，是具有 ${\xi }_j,j=1,\cdots ,N$ 元素的特征基和 $\Theta =diag\left\{{\upsilon }_1,\cdots ,{\upsilon }_N\right\}$ 是对应的对角特征值矩阵。

对于滤波器H来说， $H=h\left(P\right)=h\left(\Xi \Theta {\Xi }^{-1}\right)={\displaystyle \underset{m=0}{\overset{M-1}{\sum }}{h}_m{\left(\Xi \Theta {\Xi }^{-1}\right)}^m}=\Xi h\left(\Theta \right){\Xi }^{-1}$ ，其中 $h\left(\Theta \right)$ 为对角矩阵， $h\left(\Theta \right)=diag\left\{h\left({\upsilon }_1\right),\cdots ,h\left({\upsilon }_N\right)\right\}$ 。进而可以证明P的特征向量相对于图滤波器的不变性： $H{\xi }_m=\Xi h\left(\Theta \right){\Xi }^{-1}{\xi }_m=\Xi h\left(\Theta \right)e_m=h\left({\upsilon }_m\right)e_m$ 。

给定一个图信号s，其傅里叶变换用 $\hat{s}=\left[{\hat{s}}_1,\cdots ,{\hat{s}}_N\right]$ 表示， $\hat{s}=Fs={\Xi }^{-1}s$ ，其中 ${\left\{{\hat{s}}_j\right\}}_{j=1}^N$ 表示图信号在傅里叶变换后的形式。

对于特征基 $\Xi$ 的有向图的傅里叶反变换由 $s=F^{-1}\hat{s}=\Xi \hat{s}$ 给出。

原始信号的频率内容通过形成傅里叶系数加权的特征向量的线性组合重建原始信号。更一般地说，任何 ${\overline{{\rm P}}}_{\alpha }\in \bar{P}$ 都允许进行特征值分解 ${\overline{{\rm P}}}_{\alpha }={\Xi }_{\alpha }{\Theta }_{\alpha }{\Xi }_{\alpha }^{-1}$ 。

因此，可以定义在有向图上的函数构造无穷多的傅里叶基 ${\left\{{\Xi }_{\alpha }\right\}}_{\alpha \in \left[0,1\right]}$ 。

定理4.1 广义的Parseval定理给定 $\overline{{\rm P}}$ 的特征基 ${\Xi }_{1/2}$ 在 ${\mathcal{l}}^2\left(\nu ,\pi \right)$ 内是正交的，对应的傅里叶变换是从 ${\mathcal{l}}^2\left(\nu ,\pi \right)$ 到 ${\mathcal{l}}^2\left(\left\{1,\cdots ,N\right\}\right)$ ， $\langle {\Xi }_{1/2}^{-1}x,{\Xi }_{1/2}^{-1}y\rangle ={\langle x,y\rangle }_{\pi },\forall x,y\in {\mathcal{l}}^2\left(\nu ,\pi \right)$ 。

4.2. 图上信号的规律性

图信号可以通过测量变化或规律性来分析。首先定义了一个给定顶点的图形梯度的长度。

定义4.1 设 $\varsigma =\left(\nu ,\epsilon \right)$ 是一个有向图， $q:\epsilon \to {ℝ}_{+}$ 是定义在边集 $\epsilon$ 上的一个正测度。任意图 $\varsigma$ 在测度 $\nu$ 下，图信号f在顶点 $x\in \nu$ 的图梯度的长度为 $\left|\nabla f\left(x\right)\right|={\left(\frac{1}{2}{\displaystyle \underset{y\in \nu ,\left(x,y\right)\in \epsilon }{\sum }{\left|f\left(x\right)-f\left(y\right)\right|}^{2}q\left(x,y\right)}\right)}^{1/2}$ 。

图形梯度的长度度量了围绕给定顶点的图形信号的变化。引入狄利克雷能量作为信号在强连通图上变化的度量。

定义4.2 强连通图 $\varsigma$ 上具有过度矩阵P和平稳分布 $\pi$ 的遍历随机游走 $\aleph$ 的图信号f的狄利克雷能量为 $D_{\pi ,P}^2\left(f\right)=\frac{1}{2}{\displaystyle \underset{\left(x,y\right)\in \epsilon }{\sum }\pi \left(x\right)p\left(x,y\right){\left|f\left(x\right)-f\left(y\right)\right|}^2}={\langle f,L_{RW}f\rangle }_{\pi }$ 。

对于所有的 ${\overline{{\rm P}}}_{\alpha }\in \bar{P}$ ，相关狄利克雷能量是相同的： $D_{\pi ,{\overline{{\rm P}}}_{\alpha }}^2\left(f\right)=D_{\pi ,{\rm P}}^2\left(f\right)={\langle f,L_{RW}f\rangle }_{\pi }$ 。

接着引入了与狄利克雷能量 $D_{\pi ,{\rm P}}^2\left(f\right)$ 相关的图信号的瑞利商为 $R_{\pi ,{\rm P}}\left(f\right)=\frac{D_{\pi ,{\rm P}}^2\left(f\right)}{{\Vert f\Vert }_{\pi }^2}$ 。

对于任意的 ${\overline{{\rm P}}}_{\alpha }\in \bar{P}$ ，有 $R_{\pi ,{\rm P}}\left(f\right)=R_{\pi ,{\overline{{\rm P}}}_{\alpha }}\left(f\right)$ 。

4.3. 有向图的频率分析

下面命题解决了遍历随机游走 $\aleph$ 的过渡矩阵P的特征向量的正则性与其相关的特征值之间的关键联系。

命题4.1 设 $\xi \in {ℂ}^N$ 是遍历随机游走 $\aleph$ 的过度矩阵P的特征向量，具有平稳分布 $\pi$ 与特征值 $\nu \in ℂ$ 相关联，定义 $\xi$ 的瑞利商为 $R_{\pi ,{\rm P}}\left(\xi \right)=1-{\Re }_{\mathcal{l}}\left(\nu \right)$ ，其中 ${\Re }_{\mathcal{l}}\left(\nu \right)$ 表示 $\nu \in ℂ$ 的实部。

接下来的命题表明，P的任意特征向量 $\xi$ 的变化，如其瑞利商所描述，与其各自特征值的实部 $\nu$ 相关，更一般地说， ${\overline{{\rm P}}}_{\alpha }\in \bar{P}$ 的任何特征向量 ${\xi }_{\alpha }$ 的变化特征与命题4.1完全相同，即： $R_{\pi ,{\rm P}}\left({\xi }_{\alpha }\right)=1-{\Re }_{\mathcal{l}}\left({\nu }_{\alpha }\right)$ 。

因此，能够将P的特征向量 $\xi$ 和给定 ${\overline{{\rm P}}}_{\alpha }\in \bar{P}$ 的每个特征向量 ${\xi }_{\alpha }$ 联系起来，一个表征其变化的值 $\omega$ ，称之为频率，记为 $\omega =1-{\Re }_{\mathcal{l}}\left(\nu \right),\omega \in \left[0,2\right]$ 。

命题4.2 在无向条件下，随机游走是可逆的，因此与随机游走算子P相关的狄利克雷能量为 $D_{\pi ,{\rm P}}^2\left(f\right)={\langle f,L_{RW}f\rangle }_{\pi }$ ，其中 $L_{RW}={\rm I}-{\rm P}$ 。随机游走算子P在 ${\mathcal{l}}^2\left(\nu ,\pi \right)$ 中是自伴随的，因此，给定P一个特征向量 $\xi$ 与特征值 $\nu$ 相关，相关的瑞利商为 $R_{\pi ,{\rm P}}\left(\xi \right)=1-\nu$ 。因此，P的特征向量的变化与各自特征值直接相关。

4.4. 随机游走图滤波器

将随机游走图滤波器定义关于参考算子的LSI滤波器为 ${\rm H}={\displaystyle \underset{t=0}{\overset{{\rm T}}{\sum }}{h}_t{{\rm P}}^t}$ 。假设P是可对角化的，可以将图滤波器表示为与相关的光谱投影仪 ${\left\{{{\rm E}}_{{\nu }_k}\right\}}_{k=1}^m$ 的线性组合，即 ${\rm H}={\displaystyle \underset{k=1}{\overset{m}{\sum }}{\gamma }_k{{\rm E}}_{{\nu }_k}},{\gamma }_k\in ℂ,k=1,\cdots ,m$ ，其频谱系数仅依赖于频率： ${\gamma }_k=h\left({\omega }_k\right)=h\left(1-{\Re }_{\mathcal{l}}\left({\nu }_k\right)\right)$ ，其中 $h:ℝ\to ℂ$ 是滤波器的频率响应。

该滤波器在傅里叶域中由其谱响应系数表征。

定义与投影仪相关的频率 $\omega$ 为 $S_{\omega }={\displaystyle \underset{\nu :1-{\Re }_{\mathcal{l}}\left(\nu \right)=\omega }{\sum }{{\rm E}}_{\nu }}$ 。它是一个投影仪，投影在频率 $\omega$ 对应的特征空间的和上。称 $S_{\omega }$ 为与频率 $\omega$ 相关的单频投影仪。基于频率响应的滤波器可以表示为： ${{\rm H}}_{\omega }={\displaystyle \underset{\omega \in \omega }{\sum }h\left(\omega \right)S_{\omega }},\omega \in \left[0,2\right]$ 。

这个公式的一个主要优点是：允许沿着频率轴移动、收缩或扩大滤波器，只需对其频率响应应用这些操作。

在图形信号中进行滤波过程如下 [18] ：

$S_{out}=H\cdot S_{in}=\Xi h\left(\Theta \right)\left({\Xi }^{-1}{S}_{in}\right)=\Xi diag\left[h\left({\upsilon }_1\right),\cdots ,h\left({\upsilon }_N\right)\right]{\hat{S}}_{in}=\Xi \left[h\left({\upsilon }_1\right){\hat{S}}_{in},\cdots ,h\left({\upsilon }_N\right){\hat{S}}_{in}\right]$

首先可以对输入的 $S_{in}$ 执行图形傅里叶变换 ${\Xi }^{-1}{S}_{in}$ ，接着在图傅立叶变换信号 ${\hat{S}}_{in}$ 的频域中逐点乘以由滤波器频率响应 ${\left[h\left({\upsilon }_1\right),\cdots ,h\left({\upsilon }_N\right)\right]}^{\text{T}}$ 。最后，逆图傅立叶变换计算图节点域中的输出。这就是图傅立叶滤波定理，它将图滤波简化为两个图傅立叶变换和谱域中的逐点乘法。

5. 有向图上的小波分析及多分辨率分析

前面章节提到了有向图上的傅里叶样基，作为随机游走特征向量的集合，并通过研究他们来确定频率分析。这允许定义低通、高通滤波器，从而在有向图上构造出函数的多分辨率分析。首先，提出由分析图和合成图滤波器组组成的小波框架，这种多尺度结构与扩散多项式框架和谱图小波密切相关。其次，提出了一个有向图的临界采样小波结构，推广了扩散小波框架。

5.1. 有向图上的谱小波变换

提出有向图上的冗余小波变换，在无向图和多项式扩散框架上构造谱小波。新颖之处在于在频域通过频响函数作为 $S_{\omega }={\displaystyle \underset{\nu :1-{\Re }_{\mathcal{l}}\left(\nu \right)=\omega }{\sum }{{\rm E}}_{\nu }}$ 中定义的单频投影器的线性组合来设计滤波器，介绍了在有向图上构造冗余小波的必要元素。

理论框架

设 $\varsigma =\left(\nu ,\epsilon \right)$ 是基数为 $\left|\nu \right|=N$ 的强连通有向图。 $\varsigma$ 由其邻接矩阵 $W\in {ℝ}_{+}^{N\times N}$ 来刻画。在 $\varsigma$ 上定义了一个随机游走算子 $\aleph$ ，其特征是它的转移矩阵 ${\rm P}=D^{-1}W\in {ℝ}_{+}^{N\times N}$ 。设 ${\rm T}={\prod }^{1/2}{\rm P}{\prod }^{-1/2}\in {\mathcal{l}}^2\left(\nu \right)$ 是在 ${\mathcal{l}}^2$ 中类似于P的算子。

假设T可对角化。在图像处理框架中，低通、高通和带通频响的概念与参考算子的特征向量的频率是有关的。让 ${\omega }_1\le \cdots \le {\omega }_N$ 是随机游走图的频率，从最低频率 ${\omega }_1$ 到最高频率 ${\omega }_N$ 。设 ${{\rm H}}_{\omega }$ 为 ${{\rm H}}_{\omega }={\displaystyle \underset{\omega \in \omega }{\sum }h\left(\omega \right)S_{\omega }},\omega \in \left[0,2\right]$ 中定义的图滤波器。定义随机游走的截止图频率为 ${\omega }_{cut}$ ，则理想的低通和高通频率响应和分别定义为 $h\left({\omega }_m\right)=1-g\left({\omega }_m\right)=\{\begin{array}{l}1,\text{if}{\omega }_m\le {\omega }_{cut}\\ 0,\text{if}{\omega }_m>{\omega }_{cut}\end{array}$ 。

给定两个随机游走图频率 ${\omega }_{\mathcal{l}}$ 、 ${\omega }_k$ ，且 ${\omega }_k<{\omega }_{\mathcal{l}}$ 。则理想带通频响定义为 $u\left({\omega }_k\right)=\{\begin{array}{l}1,\text{if}{\omega }_m\le {\omega }_k\le {\omega }_{\mathcal{l}}\\ 0,\text{if}{\omega }_k>{\omega }_{\mathcal{l}}\text{and}{\omega }_k<{\omega }_m\end{array}$ 。

定义5.1 强连通有向图 $\varsigma$ 上的膨胀t、 ${{\rm H}}_t$ 处的低通算子定义为 ${{\rm H}}_t={\displaystyle \underset{\mathcal{l}=1}{\overset{p}{\sum }}h\left(t{\omega }_{\mathcal{l}}\right)S_{\mathcal{l}}},t\in \mathbb{N}$ 。给出低通频响的函数 ${\left\{S_{\mathcal{l}}\right\}}_{\mathcal{l}=1}^p$ ，与频率 ${\omega }_{\mathcal{l}}$ 相关(是T的特征向量)。膨胀t与平移y处的尺度函数表示为 ${\eta }_{t,y}={{\rm H}}_t{\delta }_y$ ，其中 ${\delta }_y$ 是顶点处的克罗内克函数。

定义5.2 强连通有向图 $\varsigma$ 上膨胀t、 $G_t$ 处的带通算子定义为 $G_t={\displaystyle \underset{\mathcal{l}=1}{\overset{p}{\sum }}g\left(t{\omega }_{\mathcal{l}}\right)S_{\mathcal{l}}},t\in \mathbb{N}$ ，给出带通频率响应的函数 ${\left\{S_{\mathcal{l}}\right\}}_{\mathcal{l}=1}^p$ 与频率 ${\omega }_{\mathcal{l}}$ 的特征向量在t的扩张与平移y处的小波函数用 $g_{t,y}$ 表示， $g_{t,y}=G_t{\delta }_y$ ，其中 ${\delta }_y$ 是顶点处的克罗内克函数。

有向图上的低通和带通算子存在，从而可以在有向图上构建分解与重构滤波器。

定义5.3 将一组重构滤波器K定义为由膨胀 $t_J$ 、 $H_{t_J}$ 处的低通滤波器和一系列增加膨胀 ${\left\{t_j\right\}}_{j=1}^J$ 、 ${\left\{G_{t_j}\right\}}_{j=1}^J$ 的带通滤波器 $K=\left\{H_{t_J},G_{t_1},\cdots ,G_{t_J}\right\}$ 。

定义5.4 定义了一组分解滤波器 $\tilde{K}$ ，包括一个在膨胀 $t_J$ 、 ${\tilde{H}}_{t_J}^G$ 的滤波器和一系列在增加膨胀 ${\left\{t_j\right\}}_{j=1}^J$ 、 ${\left\{{\tilde{G}}_{t_j}\right\}}_{j=1}^J$ 的滤波器， $\tilde{K}=\left\{{\tilde{H}}_{t_J},{\tilde{G}}_{t_1},\cdots ,{\tilde{G}}_{t_J}\right\}$ ，其中 ${\widetilde{{\rm H}}}^G{}_{t_J}={\displaystyle \underset{\mathcal{l}=1}{\overset{p}{\sum }}\tilde{h}\left(t{\omega }_{\mathcal{l}}\right)S_{\mathcal{l}}},t\in \mathbb{N}$ ， ${\tilde{G}}_{t_j}={\displaystyle \underset{\mathcal{l}=1}{\overset{p}{\sum }}\tilde{g}\left(t{\omega }_{\mathcal{l}}\right)S_{\mathcal{l}}}$ ， $\forall j=1,\cdots ,J$

还定义了 ${\tilde{\eta }}_{t,k}={\delta }_k^T{\widetilde{{\rm H}}}_t$ 、 ${\tilde{g}}_{t,k}={\delta }_k^T{\tilde{G}}_t$ 为行向量。

命题5.1 给定一个增加膨胀的固定集合 ${\left\{t_j\right\}}_{j=1}^J$ ，重构与分解滤波器分别为K、 $\tilde{K}$ ，完美重构的条件 ${{\rm H}}_{t_J}{\widetilde{{\rm H}}}_{t_J}+{\displaystyle \underset{j=1}{\overset{J}{\sum }}{G}_{t_j}{\tilde{G}}_{t_j}={\rm I}}$ 成立，当且仅当 $h\left(t_J{\omega }_{\mathcal{l}}\right)\tilde{h}\left(t_J{\omega }_{\mathcal{l}}\right)+{\displaystyle \underset{j=1}{\overset{J}{\sum }}g\left(t_j{\omega }_{\mathcal{l}}\right)\tilde{g}\left(t_j{\omega }_{\mathcal{l}}\right)}=1,\forall \mathcal{l}=1,\cdots ,p$ 。

接下来定义框架：

定义5.5 设 $\varsigma =\left(\nu ,\epsilon \right)$ 为一个有向图，在 $\nu$ 上的测度为 $\mu$ 。一个可数元素族 ${\left\{f_k\right\}}_{k=1}^n\in {\mathcal{l}}^2\left(\nu \right)$ 称为一个框架：若对任意图信号 $f\in {\mathcal{l}}^2\left(\nu \right)$ 有 $A{\Vert f\Vert }^2\le {\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left|\langle f,f_k\rangle \right|}^2}\le B{\Vert f\Vert }^2$ ，其中 $0<A\le B<\infty$ 为帧边界。

引入矩形矩阵 $K=\left\{H_{t_J},G_{t_1},\cdots ,G_{t_J}\right\}\in {ℝ}^{N\times N\left(J+1\right)}$ ，其中 $K=\left({\eta }_{t_J,1},\cdots ,{\eta }_{t_J,N},g_{t_1,1},\cdots ,g_{t_J,1},\cdots ,g_{t_J,N}\right)\in {ℝ}^{N\times N\left(J+1\right)}$ 。

引入矩形矩阵 $\tilde{K}={\left\{{\tilde{H}}_{t_J},{\tilde{G}}_{t_1},\cdots ,{\tilde{G}}_{t_J}\right\}}^{{\rm T}}\in {ℝ}^{N\left(J+1\right)\times N}$ ，其中 $\tilde{K}={\left({\tilde{\eta }}_{t_J,1},\cdots ,{\tilde{\eta }}_{t_J,N},{\tilde{g}}_{t_1,1},\cdots ,{\tilde{g}}_{t_J,1},\cdots ,{\tilde{g}}_{t_J,N}\right)}^{{\rm T}}\in {ℝ}^{N\left(J+1\right)\times N}$ 。

命题5.2 设K、 $\tilde{K}$ 分别表示重构与分解滤波器，根据命题4.1可知，滤波器K和 $\tilde{K}$ 符合完美重构条件，那么 $\tilde{K}$ 是 ${\mathcal{l}}^2\left(\nu \right)$ 中的一个框架， $1/{\Vert K\Vert }^2$ 和 ${\Vert \tilde{K}\Vert }^2$ 为帧边界。

定义5.6 (有向图上信号的小波分解)任意图信号 $f\in {\mathcal{l}}^2\left(\nu \right)$ 可以表示为： $f={\displaystyle \underset{k=1}{\overset{N}{\sum }}\langle f,{\tilde{\eta }}_{t_J,k}\rangle {\tilde{\eta }}_{t_J,k}}+{\displaystyle \underset{j=1}{\overset{J}{\sum }}{\displaystyle \underset{k=1}{\overset{N}{\sum }}\langle f,{\tilde{g}}_{t_j,k}\rangle {\tilde{g}}_{t_j,k}}}$ 。

5.2. 有向图上的扩散小波变换

5.2.1. 扩散小波

扩散小波构造的起点是扩散算子 $t_0$ ，与经典的多分辨率分析类似。扩散小波的特征是一组嵌套的子空间 $V_0\supseteq V_1\supseteq \cdots \supseteq V_j\supseteq \cdots$ ，其中每个子空间 $V_j$ 由缩放函数 ${\varphi }_j$ 的基张成， $V_{j+1}$ 到 $V_j$ 的补称为 $W_j$ ，由一组扩散小波 ${\psi }_j$ 张成。

5.2.2. 构造

扩散小波的构造是在强连通有向图 $\varsigma =\left(\nu ,\epsilon \right)$ 上定义扩散算子T的情况下进行的。在Coifman和Maggioni的原始的扩散小波框架中，假设图是无向的，建议使用随机游走逆算子P。只要作用类似于低通滤波器就可以用来使用。若给定有向图，则选择算子 ${\rm T}={\Pi }^{1/2}{\rm P}{\Pi }^{-1/2}$ ，其中P是随机游走算子。随机游走算子并不保证具有低频响应，那么低通滤波器便可以用惰性随机游走来定义： ${\rm T}={\Pi }^{1/2}\left(\gamma {\rm I}+\left(1-\gamma \right)P\right){\Pi }^{-1/2}$ 。

假设T最初是用 $V_0$ 中的正则基 ${\varphi }_0={\left\{{\delta }_k\right\}}_{k\in \nu }$ 来表示，其中 ${\delta }_k$ 是顶点对应的Kronecker delta函数。 ${\left[{\tilde{\varphi }}_{1,k}\right]}_{{\Phi }_0}={\left[{\rm T}\right]}_{{\Phi }_0}^{{\Phi }_0}{\delta }_k$ 是线性算子T关于定义域内基 ${\varphi }_1$ 的元素 ${\varphi }_{1,k},k\in \nu$ 。T的低通性导致了这样的事实，即 ${\tilde{\varphi }}_1$ 的某个元素 ${\tilde{\varphi }}_{1,k}$ 是函数其顶点k进行局部化的函数，支持扩展到其近邻。在扩散小波结构方面，元素 ${\tilde{\varphi }}_{1,k}\in \nu$ 被称为尺度函数。由于每个函数 ${\tilde{\varphi }}_{1,k}$ 的支撑覆盖了它们各自顶点的周围的一小块邻域，这些元素 ${\tilde{\varphi }}_{1,k}$ 通常可以通过其他函数的线性组合来很好的逼近。

构造的下一阶段是列子集选择阶段。选择 ${\Phi }_1$ 中的一个子集 $\left\{{\tilde{\varphi }}_{1,k},k\in I_1\right\}$ 使得所有的 ${\tilde{\varphi }}_{1,k}$ 都可以很好地近似于子集中函数的线性组合。在经典的图像信号处理中，这一步类似于经典小波变换中一组缩放函数的子采样。

子集 $\left\{{\tilde{\varphi }}_{1,k},k\in I_1\right\}$ 张成了一个空间 $V_1$ ，该子空间对应于多分辨率分析的第一近似子空间。将 $\left\{{\tilde{\varphi }}_{1,k},k\in I_1\right\}$ 表示为 ${\Phi }_1$ ，其中根据定义 ${\Phi }_1$ 通常是不正交的基中的向量是尺度为1的尺度函数。

为了定义尺度函数的下一个尺度，考虑扩散算子T在子空间 $V_1$ 上的限制。 ${\left[{{\rm T}}^2\right]}_{{\Phi }_1}^{{\Phi }_1}\approx {\left({\left[{\rm T}\right]}_{{\Phi }_1}^{{\Phi }_1}\right)}^2$ 的列可以

解释为尺度为2的尺度函数，其中 ${\tilde{\Phi }}_2=\left\{{\tilde{\varphi }}_{2,k}\right\}$ 。从这些函数中提取出一个子集 ${\tilde{\Phi }}_2=\left\{{\tilde{\varphi }}_{2,k},k\in I_2\right\}$ ，使得 ${\tilde{\Phi }}_2$ 中的任意函数都可以被 ${\Phi }_2$ 中函数的线性组合很好地近似。

经过这一过程的迭代，定义了j个近似子空间 $V_j\subset V_{j-1}\subset \cdots \subset V_1$ ，其对应的基底为 ${\Phi }_j,{\Phi }_{j-1},\cdots ,{\Phi }_1$ 。在每一步中，基 ${\Phi }_j$ 是由其在基 ${\Phi }_{j-1}$ 中的表示定义，该表示基于运算符 ${{\rm T}}^{2j}$ 对 $V_{j-1}$ 的限制。

由于 ${\Phi }_0$ 中的每个函数都是在 $V_0$ 中定义的，因此 ${\Phi }_j$ 中的每个函数都是如此。因此，近似空间 $V_j$ 中的任何函数都可以自然扩充到整个空间 $V_0$ 中。

关于小波的构造，提出了选择带通算子 ${\left[{{\rm I}}_{V_j}-{\Phi }_{j+1}{\Phi }_{j+1}^{\hslash }\right]}_{{\Phi }_j}^{{\Phi }_j}$ 的列的子集，即 $V_{j+1}$ 对 $V_j$ 的补上的正交投

影，构造子空间 $W_j$ 的小波基 ${\psi }_j$ ，小波捕捉到了从 $V_{j+1}$ 到 $V_j$ 的过程中丢失的细节。由于框架为双正交范围，因此需要构造双小波基。对于尺度j，有个小波基 ${\Psi }_j$ ，需要构造相应的对偶基 ${\hat{\Psi }}_j$ ，从而有 ${\Psi }_j^{\text{'}\hslash }{\Psi }_j={\rm I}$ ，其中 ${\Psi }_j^{\text{'}\hslash }$ 是 ${\Psi }_j$ 的伪倒数。

6. 有向图上的紧支撑帕塞瓦尔小波框架及多分辨率分析

前面章节提出了有向图上的傅里叶变换和小波变换作为信号处理中的推广，近年来易构造性的性质良好的紧小波框架也受到重视，同样也可以在有向图中进行推广 [19] 。在上述研究时将算子限制为可对角化，从而得到了有向图的傅里叶基和小波基。现在令随机游走算子为可逆的整数项算子，在此基础上形成有向图上的紧支撑帕塞瓦尔小波框架。小波框架构成了函数的多分辨率分析，定义了低通、高通滤波。

6.1. 有向图上的紧支撑帕塞瓦尔小波框架

提出有向图上的紧支撑帕塞瓦尔小波框架。新颖之处在于可以将算子不在限制于可对角化，可以将算子的范围扩大为整数项可逆的扩张矩阵。

6.1.1. 紧支撑帕塞瓦尔小波框架

定义6.1. [20] 设 ${\left\{{\varphi }_n\right\}}_{n=1}^{\infty }$ 是可分希尔伯特空间H中元素的序列，如果存在常数 $C_1,C_2>0$ ，使得 $C_1{\Vert h\Vert }^2\le {\displaystyle \underset{n=1}{\overset{\infty }{\sum }}{\left|\langle h,{\varphi }_n\rangle \right|}^2}\le C_2{\Vert h\Vert }^2,\forall h\in H$ ，则称序列 ${\left\{{\varphi }_n\right\}}_{n=1}^{\infty }$ 为H中的一个框架。常数 $C_1$ 和 $C_2$ 称为框架界。若 $C_1=C_2$ ，那么 ${\left\{{\varphi }_n\right\}}_{n=1}^{\infty }$ 为紧框架。

定义6.2. [20] 在 $L^2\left({ℝ}^2\right)$ 中，若一个框架为 $\left\{{\psi }_{l,j,k}\left(x\right);j\in \mathbb{Z},k\in {\mathbb{Z}}^d,1\le l\le N\right\}$ ，其中 ${\psi }_{l,j,k}\left(x\right):={\left|\det A\right|}^{j/2}{\psi }_l\left(A^{j}x+k\right)$ ，则称其为与扩张矩阵A相关的小波框架。若它为紧框架，那么 $\left\{{\psi }_{l,j,k}\left(x\right);j\in \mathbb{Z},k\in {\mathbb{Z}}^d,1\le l\le N\right\}$ 被称为紧小波框架。若函数是线性无关的，则成为一族小波框架的生成器。若帧常数等于1，则称其为帕塞瓦尔小波框架。从而就有， ${\displaystyle \underset{l=1}{\overset{N}{\sum }}{\displaystyle \underset{j\in \mathbb{Z}}{\sum }{\displaystyle \underset{k\in {\mathbb{Z}}^d}{\sum }{\left|\langle f,{\psi }_{l,j,k}\left(x\right)\rangle \right|}^2}}}={\Vert f\Vert }^2,\forall f\in L^2\left({ℝ}^d\right)$ 。

定义6.3. [20] 假设图信号定义在 ${\mathcal{l}}^2\left(\nu ,\nu \right)$ 中，在 $\varsigma$ 的顶点集合 $\nu$ 上定义的函数是在希尔波特空间上。 $\varsigma$ 的顶点集 $\nu$ 被赋予了与 $\nu$ 相关的内积，其中 $\nu$ 是一个正的任意顶点度量。 ${\langle f,g\rangle }_{\nu }={\displaystyle \underset{x\in \nu }{\sum }\overline{f\left(x\right)}g\left(x\right)\nu }\left(x\right),\forall f,g$ ， $\overline{f\left(x\right)}$ 为 $f\left(x\right)$ 的复共轭。

定义6.4 令 $\hat{f}$ 表示函数的傅里叶变换，则 $\hat{f}:={\displaystyle \underset{x\in \nu }{\sum }\overline{f\left(x\right)}{\text{e}}^{-2\pi ix\cdot t}\nu }\left(x\right),\forall f,g$ ，其中 $x\cdot t$ 为向量的点积。

6.1.2. 构造

以 $\varsigma =\left(\nu ,\epsilon \right)$ 是基数为 $\left|\nu \right|=N$ 的强连通有向图为研究对象。 $\varsigma$ 由其邻接矩阵 $W\in {ℝ}_{+}^{N\times N}$ 来刻画。在 $\varsigma$ 上定义了一个随机游走算子 $\aleph$ ，其特征是它的转移矩阵 ${\rm P}=D^{-1}W\in {ℝ}_{+}^{N\times N}$ 。设 $A={\prod }^{1/2}{\rm P}{\prod }^{-1/2}\in {\mathcal{l}}^2\left(\nu \right)$ 是在 ${\mathcal{l}}^2$ 中类似于P的算子。

假设A为整数项的可逆扩张矩阵，那么A可以进行施密特正交化，即 $A=USV$ ，其中U和V为整数矩阵且 $\left|\det U\right|=\left|\det V\right|=1$ ， $S=diag\left(s_1,s_2,\cdots ,s_r,\cdots ,s_d\right)$ 为对角矩阵。存在一个整数 $r\le d$ ，当 $1\le i\le r$ 时， $s_i>1$ ，当 $i>r$ 时， $s_i=1$ 。在 $r=d$ 的情况下，所有的 $s_i$ 都将大于1，如果 $i\le r$ ，则 $s_i$ 可被 $s_{i-1}$ 整除。

在施密特正交化后，易得到商群 ${\mathbb{Z}}^d/A{\mathbb{Z}}^d$ 以及 ${\left(A^{*}\right)}^{-1}{\mathbb{Z}}^d/{\mathbb{Z}}^d$ 的完整集合形式。令 $\Gamma =\left\{\frac{0}{s_1},\frac{1}{s_1},\cdots ,\frac{s_1-1}{s_1}\right\}\times \cdots \times \left\{\frac{0}{s_r},\frac{1}{s_r},\cdots ,\frac{s_r-1}{s_r}\right\}\times \left\{0\right\}\times \cdots \times \left\{0\right\}$ ，从而有 ${\Gamma }_A:={\left\{r_a\right\}}_{a=0}^{\left|\det A\right|-1}:=\left\{{\left(U^{*}\right)}^{-1}\gamma :\gamma \in \Gamma \right\}\in {\left(A^{*}\right)}^{-1}{\mathbb{Z}}^d/{\mathbb{Z}}^d$ 、 ${\Delta }_A:={\left\{q_a\right\}}_{a=0}^{\left|\det A\right|-1}\in {\mathbb{Z}}^d/A{\mathbb{Z}}^d$ 。

引入 $ℝ$ 上的三角多项式 $p_{s,m}\left(t\right):=\left(\frac{1}{s^{2m}}\left|1+{\text{e}}^{2\pi it}+\cdots +{\text{e}}^{2\pi i\left(s-1\right)t}\right|\right)\left({\displaystyle \underset{j=0}{\overset{m-1}{\sum }}{q}_{s,m}^{\left(j\right)}{\left(1-\cos 2\pi t\right)}^j}\right)$ ，其中当 $b=s/2$ 时， $q_{s,m}^{\left(j\right)}:={\displaystyle \underset{k_1+k_2+\cdots +k_b=j}{\sum }\left\{{\displaystyle \underset{c=1}{\overset{b-1}{\prod }}\left(\begin{array}{c}2m+k_c-1\\ 2m-1\end{array}\right)}{\left(1-\cos \frac{2\pi c}{s}\right)}^{-k_c}\right\}\times \left(\begin{array}{c}2m+k_b-1\\ 2m-1\end{array}\right)}{\left(1-\cos \pi \right)}^{-k_b}$ ；当 $b=\left(s-1\right)/2$ 时， $q_{s,m}^{\left(j\right)}:={\displaystyle \underset{k_1+k_2+\cdots +k_b=j}{\sum }\left\{{\displaystyle \underset{c=1}{\overset{b}{\prod }}\left(\begin{array}{c}2m+k_c-1\\ 2m-1\end{array}\right)}{\left(1-\cos \frac{2\pi c}{s}\right)}^{-k_c}\right\}}$ 。

定理6.1. [20] 令 $D:=\left|\det A\right|$ ， $\hat{\theta }\left(A^{*}t\right)={\left|H\left(t\right)\right|}^{2n}\hat{\theta }\left(t\right)=P\left(t\right)\hat{\theta }\left(t\right)$ ，其中 $P\left(t\right)={\left|H\left(t\right)\right|}^{2n}$ 、 $H\left(t\right):=Q\left(U^{*}t\right)$ 、 $Q\left(t\right)=Q\left(t_1,t_2,\cdots ,t_d\right):={\displaystyle \underset{j=1}{\overset{r}{\prod }}{h}_{s_j,m_j}\left(t_j\right)}$ ，满足 ${\left|h_{s,m}\left(t\right)\right|}^2=p_{s,m}\left(t\right)$ 。P为前面式子中定义的 ${ℝ}^d$ 上的实值三角多项式。令 $\theta$ 满足 $\hat{\theta }\left(t\right):={\left|\hat{\varphi }\left(t\right)\right|}^{2n}$ ，且此时 $\theta$ 傅里叶变换是非零的，可细化和紧支撑的。定义 ${\hat{\psi }}_{\mathcal{l}}\left(A^{*}t\right):=D^{-\frac{1}{2}}\left[{\text{e}}^{2\pi i{q}_{\mathcal{l}}\cdot t}-P\left(t\right)\left({\displaystyle \underset{\alpha =0}{\overset{D-1}{\sum }}{\text{e}}^{2\pi i{q}_{\mathcal{l}}\cdot \left(t+r_{\alpha }\right)}}\right)P\left(t+\alpha \right)\right]\hat{\theta }\left(t\right),\forall \mathcal{l}\in \left\{0,\cdots ,D-1\right\}$ ，且 ${\hat{\psi }}_{\mathcal{l}}\left(A^{*}t\right):=P\left(t\right)F_{\mathcal{l}-D+1}\left(t\right)\hat{\theta }\left(t\right),\forall \mathcal{l}\in \left\{0,\cdots ,D+r-1\right\}$ ，其中 $F_{\mathcal{l}}\left(t\right):=G_{\mathcal{l}}\left(U^{*}t\right),\forall \mathcal{l}\in \left\{1,\cdots ,r\right\}$ 。让 $\Psi =\left\{{\psi }_{\mathcal{l}}:\mathcal{l}=0,\cdots ,D+r-1\right\}$ 为上述恒等式中定义函数的傅里叶反变换的集合。那么 $\Psi$ 是 $L^2\left({ℝ}^d\right)$ 中与扩张矩阵A相关的紧支撑帕塞瓦尔小波框架，其消失矩为 $m_0$ 阶。

说明：利用斜可拓原理OEP，当 $\hat{\theta }\left(A^{\ast }t\right)=P\left(t\right)\hat{\theta }\left(t\right)$ 中的 $P\left(t\right)$ 和 ${\hat{\psi }}_{\mathcal{l}}\left(A^{\ast }t\right)=Q_{\mathcal{l}}\left(t\right)\hat{\theta }\left(t\right)$ 中的 $Q_{\mathcal{l}}\left(t\right)$ 满足OEP条件，即满足

$S\left(A^{\ast }t\right)P\left(t\right)\overline{P\left(t+j\right)}+{\displaystyle \underset{\mathcal{l}=1}{\overset{D+r-1}{\sum }}{Q}_{\mathcal{l}}\left(t\right)\overline{Q_{\mathcal{l}}\left(t+j\right)}}=\{\begin{array}{l}S\left(t\right),j\in {\mathbb{Z}}^d\\ 0,j\in {\left(A^{\ast }\right)}^{-1}{\mathbb{Z}}^d/{\mathbb{Z}}^d\end{array}$

时，可以证明 $\text{Ψ}=\left\{{\psi }_{\mathcal{l}}:\mathcal{l}=0,\cdots ,D+r-1\right\}$ 是在中与扩张矩阵A相关的紧支撑帕塞瓦尔小波框架。

其次证明了生成器 ${\psi }_{\mathcal{l}},\mathcal{l}=0,\cdots ,D+r-1$ 是具有 $m_0$ 阶消失矩的，只要证明

$\underset{t\to 0}{\lim }\frac{{\left|{\hat{\psi }}_{\mathcal{l}}\left(A^{\ast }t\right)\right|}^2}{{\Vert A^{\ast }t\Vert }^{2m_0}}=0$ 。

定理6.2. [20] 对于任何包含积分项的扩张矩阵 $A\in R^{d\times d},d\ge 1$ ，可以在 $L^2\left({ℝ}^d\right)$ 构造一族紧支撑帕塞瓦尔小波框架。这一族小波框架的生成器依赖于扩张矩阵A与维数d，但不超过 $\left|\det A\right|+d$ 。

这时就构成了有向图上的紧支撑帕塞瓦尔小波框架。

6.2. 有向图中基于紧支撑帕塞瓦尔小波框架的频率分析

这一节明确了与遍历随机游走 $\aleph$ 的过渡矩阵P有关的特征向量与其相关的特征值之间的关键联系。

设 $A={\prod }^{1/2}{\rm P}{\prod }^{-1/2}\in {\mathcal{l}}^2\left(\nu \right)$ 是在 ${\mathcal{l}}^2$ 中类似于P的算子，此算子为整数项可逆的扩张矩阵。A可以进行施密特正交化，即 $A=USV$ ，其中U和V为酉矩阵且 $\left|\det U\right|=\left|\det V\right|=1$ ， $S=diag\left(s_1,s_2,\cdots ,s_r,\cdots ,s_d\right)$ 为半正定的对角矩阵。

奇异值分解中，先 $A{A}^{-1}$ 对做特征值分解：由于 $A{A}^{-1}=US{S}^{-1}{U}^{-1}=U\Lambda U^{-1}$ ，此时特征值为 ${\left|s_i\right|}^2$ 对应的特征向量 $\xi$ 组成了U；接着对先 $A^{-1}A$ 对做特征值分解：由于 $A^{-1}A=V{S}^{-1}S{V}^{-1}=V{\Lambda }^{\prime }{V}^{-1}$ ，此时特征值仍为 ${\left|s_i\right|}^2$ 对应的特征向量 ${\xi }^{\prime }$ 组成了V。

设上述提到的特征向量具有平稳分布 $\pi$ ，通过奇异值分解过程就能够将与A相关的特征向量 $\xi$ 和 ${\xi }^{\prime }$ 用瑞利商与特征值相关的 ${\left|s_i\right|}^2$ 联系起来，用频率 $\omega$ 来表征其变化的值： $\omega =R_{\pi ,{\rm P}}\left(\xi \right)=R_{\pi ,{\rm P}}\left({\xi }^{\prime }\right)=1-{\Re }_{\mathcal{l}}\left({\left|s_i\right|}^2\right)$ 。

因此，与A相关的特征向量的变化与其有关特征值间接相关。

6.3. 有向图中基于紧支撑帕塞瓦尔小波框架的多分辨率分析

基于小波框架的构造，经过反傅里叶变换及相关计算，最终可以得到与扩张矩阵A相关的紧支撑帕塞瓦尔小波框架

$\left\{{\psi }_{\mathcal{l},j,k}\left(x\right);j\in {\mathbb{Z}}^d,1\le \mathcal{l}\le N\right\}$

其中

${\psi }_{\mathcal{l},j,k}\left(x\right):={\left|\det A\right|}^{j/2}{\psi }_{\mathcal{l}}\left(A^{j}x+k\right)\subset L^2(\; ℝ\; d\; )$

这是由尺度函数 $\theta \left(A^{j}x+k\right)$ 定义的小波框架序列。

$V_j$ 是由尺度函数 $\theta \left(A^{j}x+k\right)$ 张成的空间。 $V_j$ 是 $V_{j+1}$ 的真子空间，令 $W_j$ 是 $V_j$ 在 $V_{j+1}$ 中的补空间，则有 $V_{j+1}=V_j+W_j$ ，而且 $W_j$ 是由小波框架 ${\psi }_{\mathcal{l},j,k}\left(x\right)$ 张成的小波子空间，即 $W_j=span{\left\{{\psi }_{\mathcal{l},j,k}\left(x\right)\right\}}_{k\in Z}$ 。

由于 ${\left\{V_j\right\}}_{j\in Z}$ 是由尺度函数 $\theta$ 生成的空间，满足如下条件 [21] ：

1) 单调性： $\cdots \subset V_{j-1}\subset V_j\subset V_{j+1}\subset \cdots ,\forall j\in \mathbb{Z}$ ；

2) 逼近性： ${\displaystyle \underset{j\in \mathbb{Z}}{\cap }{V}_j}=\left\{0\right\}\text{,}\stackrel{¯}{{\displaystyle \underset{j\in \mathbb{Z}}{\cup }{V}_j}}=L^2\left({ℝ}^2\right)$ ；

3) 伸缩性： $f\left(x\right)\in V_j\iff f\left(Ax\right)\in V_{j+1},\forall j\in \mathbb{Z}$ ；

4) 平移不变性： $f\left(x\right)\in V_j\iff f\left(x+k\right)\in V_j,\forall j\in \mathbb{Z},k\in {\mathbb{Z}}^d$ ；

5) 存在 $\theta \in V_0$ ，使得 $\theta \left(x+k\right)$ 构成空间 $V_0$ 的一个框架。

故 ${\left\{V_j\right\}}_{j\in Z}$ 是由尺度函数 $\theta$ 生成的框架多分辨分析(FMRA)。

6.4. 有向图中基于紧支撑帕塞瓦尔小波框架的滤波

与前面傅里叶函数与小波函数一样，此框架也随着算子的不同而发生改变，同样低通、高通滤波器也随之改变，具有针对性。这种紧支撑帕塞瓦尔小波框架构造简便且性质良好。

有向图中得到的特定算子A基于多分辨率分析思想，按照小波框架与尺度函数的对应关系进行分解，可以得到特定的系数，其中小波框架 ${\psi }_{\mathcal{l},j,k}\left(x\right)$ 前的系数可以构成高通滤波，尺度函数 $\theta \left(A^{j}x+k\right)$ 前的系数构成低通滤波。

设信号

$f_j\left(x\right)={\displaystyle \underset{k\in {\mathbb{Z}}^d}{\sum }{a}_k^j\theta \left(A^{j}x+k\right)}\in V_j$ ，

则 $f_j\left(x\right)$ 可以分解成下列形式

$f_j\left(x\right)=w_{j-1}\left(x\right)+f_{j-1}(\; x\; )$

其中 $w_{l-1}\left(x\right)={\displaystyle \underset{k\in {\mathbb{Z}}^d}{\sum }{\displaystyle \underset{\mathcal{l}=1}{\overset{D}{\sum }}{b}_{\mathcal{l}k}^{j-1}{\left|\det A\right|}^{\left(j-1\right)/2}{\psi }_{\mathcal{l}}\left(A^{j-1}x+k\right)}}\in W_{j-1}$ ， $f_{l-1}\left(x\right)={\displaystyle \underset{k\in {\mathbb{Z}}^d}{\sum }{a}_k^{j-1}\theta \left(A^{j-1}x+k\right)}\in V_{j-1}$ 。

此时 $\left\{b_{\mathcal{l}k}^{j-1}\right\}$ 构成 $\mathcal{l}$ 组高通滤波， $a_k^{j-1}$ 构成低通滤波。

同理，重构的滤波也是如此。

假设 $f_n\left(x\right)={\displaystyle \underset{j=1}{\overset{n-1}{\sum }}{w}_j\left(x\right)}+f_0\left(x\right),w_j\left(x\right)\in W_j$ ，其中 $f_0\left(x\right)={\displaystyle \underset{k\in {\mathbb{Z}}^d}{\sum }{a}_k^0\theta \left(x-k\right)}\in V_0$ 、 $w_j\left(x\right)={\displaystyle \underset{k\in {\mathbb{Z}}^d}{\sum }{\displaystyle \underset{\mathcal{l}=1}{\overset{D}{\sum }}{b}_{\mathcal{l}k}^j{\left|\det A\right|}^{j/2}{\psi }_{\mathcal{l}}\left(A^{j}x+k\right)}}\in W_j,0\le j\le n-1$ 。

则函数前系数即可以构成低通、高通滤波。

7. 结论

引入了一种新的有向图的谐波分析方法。首先，基于有向图上随机游动算子的特征向量，回顾了有向图定义函数的频率分析。接着，从这种傅立叶型频率解释中，展示了如何通过推广扩散小波框架来构造有向图上的冗余小波以及临界采样小波。最后，基于扩展到了整数项的扩张矩阵中的随机游走的相关算子，构造了紧支撑帕塞瓦尔小波框架，根据奇异值的分解过程找到了在此基础上的频率解释，并提出了多分辨率分析，进而得到滤波。紧支撑帕塞瓦尔小波框架的构造简单，并且具有确定的消失矩，这将更利于数据网络的分析和处理。