图信号的采样理论

tags: '图信号处理' '采样'

论文信息

• Paper: [IEEE Transactions on Signal Processing 63 (24)] Discrete signal processing on graphs: Sampling theory [1]
• Link: https://arxiv.org/pdf/1503.05432

背景梳理

对于一个普通的离散时间信号，采样和恢复是极为重要的议题。在传统的信号与系统以及数字信号处理理论中，如果一个信号的采样率高过其最高频率的两倍，我们就能够完美的恢复原始信号。这是信号处理领域著名的奈奎斯特采样定理：

上式中表示采样频率，被采样信号中的最高频率分量。 自然而然，我们希望将采样的完美恢复条件扩展的图信号处理当中。例如社交网络的分析当中，如果能够采样部分用户数据获得完整的全局信息，自然能为图信号处理带来新的优势。本文作者及其敏锐地发现了采样理论在时间信号和图信号中的联系和不同，发现了在图傅立叶变换下限带的图信号，完美的恢复是可能的。采样后的信号系数将形成一个新的图信号，其对应的图结构保留了原始图信号的一阶差分。对于一般图，作者提出了最优采样算子，以保证完美的恢复和对噪声的鲁棒性；对于图傅立叶变换是Frames With Maximal Robustness to Erasures的图以及 Erdős-Rényi图，随机采样后可以完美恢复的概率是非常高的。 本文的主要贡献包括以下三点： • 提出了一种新颖的图形信号采样框架，通过使用线性代数中的简单工具解决了复杂的采样问题； • 提出了一种通过保留原始图形信号中的一阶差分来对图形进行采样的新方法； • 一种在图上设计采样算子的新方法。

图的基本定义

图移位操作

对于一个图上的离散信号处理，我们用来表示一个具有复杂结构的图，其中是节点的集合，是图移位矩阵，也就是图的邻接矩阵，其表征了图的连接关系，可表示有向图和无向图（标准的图拉普拉斯矩阵式是只能表述无向图的关系）。为了保证以为操作数值尺度合理，我们将移位矩阵归一化使其满足。

图信号

在给定的图表征中，图信号被定义为图节点上的映射，它将信号系数分配给节点。 一旦节点顺序固定，图信号可以写成一个向量:

其中第n个信号洗漱表征节点上的响应。

图傅立叶变换

通常来说，傅立叶变换对应于使用具有滤波不变性的基元素对信号进行分解。在这里，这个基是图移位矩阵的特征基（或者，如果完整的特征基不存在，则是的Jordan特征基）。为简单起见，假设具有完整的特征基并且的分解为:

其中，矩阵V的行为特征矩阵A的特征向量。而是由矩阵的特征值构成的对角矩阵。 接下来，我们定义图信号的傅立叶变换为：

逆变换为：

向量表示信号在该组特征基上的系数，描述图形信号的频率内容。图傅立叶逆变换通过组合由信号图傅立叶变换的系数加权的图频率分量，从其频率内容重建图信号。

采样的基本定义

采样和重建

我们希望从一个图信号采样M个系数来产生一个采样信号，其中表示采样索引，。 而插值则指的是将转为，该恢复信号能与原始信号完全或者近似相等。采样操作可以用一个从到的线性映射表示，我们定义为:

对应的插值操作则是从到的线性映射。我们将这两个过程写作矩阵形式：

带限信号

我们将带限图信号定义为： 当存在一个使得图信号的的图傅立叶变换满足：

最小的符合条件的被称为信号的带宽。一个非带限的图信号被称作是全带图信号。 请注意，此处的带限图信号不一定意味着低通或平滑。 由于我们没有指定频率的顺序，我们可以重新排序特征值并置换图傅立叶变换矩阵中的相应特征向量以选择图傅立叶域中的任何波段。 只有当我们按降序对特征值进行排序时，带限图信号才是平滑的。 这里的带限限制等效于限制已知支持的图傅立叶域中非零信号系数的数量。这种概括对于表示非光滑图信号可能有用。 特别需要注意的是：在定义带宽时，我们关注图频率的数量，而之前的工作 [2] 则关注图频率的值。使用图频率值有两个缺点：

• (a)在考虑图频率值时，我们忽略了图的离散性；因为图频率是离散的，所以同一图上的两个截止图频率可以导致相同的带限空间。例如，假设一个图的图频率为 0、0.1、0.4、0.6 和 2；当我们将截止频率设置为 0.2 或 0.3 时，它们会导致相同的带限空间；
• (b) 图频率值不能在不同图之间进行比较。由于每个图都有自己的图频率，因此两个图上截止图频率的相同值可能意味着不同的事情。例如，一个图的图频率为 0、0.1、0.2、0.4 和 2，另一个图的图频率为 0、1.1、1.6、1.8 和 2；当我们将截止频率设置为 1 时，即我们保留所有不大于 1 的图频率，第一个图保留了四个图频率中的三个，第二个图仅保留了四个图频率中的一个。因此，图频率的值不一定能直接直观地理解带限空间。使用图形频率数量的另一个关键优势是建立与线性代数的关系，允许使用线性代数中的简单工具对带限图形信号进行采样和插值。

采样恢复的条件

从之前采样和恢复的矩阵表达式中我们可以发现，要想采样后的信号能够完美恢复，则必须满足

这意味着相乘的结果为单位矩阵。

接下来我们从代数的角度来看这个问题，首先我们定义：

其中表示矩阵的前K行。完美恢复只有在：

的时候才会达成，其中是一个的单位矩阵。 当 时，，因此，永远不可能是单位矩阵。 对于是单位矩阵，当 时， 是 的逆； 当 时，它是的伪逆，其中冗余可用于减少噪声的影响。 为简单起见，我们只考虑 和 可逆。 当 时，我们只需从 个采样信号系数中选择 个，以确保样本大小和带宽相同。

采样后的图信号

首先补充一个定义：（为保证描述准确，这里使用英文原文） Definition: The set of graph signals in with bandwidth of at most is a closed subspace denoted , with as in 接下来我们考虑的情况： 当采样操作满足前文所述恢复条件时，对所有的,有下式：

其中表示的前个系数。结合之前所述我们可以得到：

这说明采样信号和可以构成一个傅立叶对，进而我们得到这个信号是关联于图移位矩阵的一个图信号：

采样后图信号的特性

我们认为是采样后的图移位矩阵。在采样过程中，究竟什么信息被所保存下来？接下来本文将讨论这个问题，首先给出结论：

证明如下：

由于项表征的是原始信号和移位信号之间的差，这也被称作的一阶差分。而则表征的是采样过后信号的一阶差分。当然这里也可以用p阶范数，总之是用来表示图信号的平滑程度。当使用采样图来表示采样信号系数时，我们丢失了采样节点与所有其他节点之间的连通性信息； 尽管如此，仍然保留采样索引处的一阶差分信息。

合格采样算子的采样

如前文所述，只有合格的采样算子才能完美恢复带限图形信号。由于合格的抽样算子是通过图结构设计的，该设计包括在中找到个线性独立的行，这提供了多种选择。在本节中，我们提出了一种通过最小化一般图的噪声影响来设计合格采样算子的最佳方法。 然后我们表明，对于一些特定的图，随机抽样也导致高概率的完美恢复。

实验设计信号

我们考虑在采样过程中引入噪声的模型如下：

其中是一个可恢复的采样，

为了限制误差范围

从上式中可以看出，因为和是确定量，要想让上界变小，只能使变小。这等价于最大化的最小化奇异值。可将该优化问题定义为：

可以用以下贪心算法获得最优采样算子：

随机采样

这里我们着重介绍Erdo ̋s-Re ́nyi图（下文用E图代指）。 Erdo ̋s-Re ́nyi 图是通过随机连接节点构建的，其中每条边都包含在图中，概率 p 独立于任何其他边。我们旨在证明通过随机采样 K 个信号系数，对应的 Ψ V(K) 的奇异值是有界的。 我们让图移位算子表示一个E图，节点之间的连接彼此独立，概率为，同时是某个正函数。我们让V为A的特征向量组成的矩阵（）,同时是采样数M满足：

其中为正常数，有以下结论

（证明位于参考文献[3]的定理1.2）

根据上式的结论，我们可以得出结论：令按上式定义。可以以的概率，使的奇异值落在到中（有上下界）。 证明如下： 首先根据上式，可得：

于是，对于所有的,有

从上式中，我们看到的奇异值有很高的概率有界。这表明 ΨV(K) 具有高概率满秩； 换句话说，当我们随机采样足够数量的信号系数时，对于E图信号，很有可能实现完美的恢复。 对于该结论，作者进行了仿真实验 上图显示了 50 和 500 大小的图在 100 次随机测试中的平均成功率。 当我们固定图大小时，在E图中，成功率随着连接概率的增加而增加，即两节点越容易产生连接，得到合格抽样算子的概率越高。 当我们比较节点间连接概率相同的的不同大小图时，采样恢复成功率随着大小的增加而增加，即较大的图大小导致获得合格抽样算子的概率更高。模拟结果表明，当图上存在更多连接时，更容易满足满秩假设。直觉是，在连接概率较高的较大图中，节点之间的差异较小，即每个节点具有相似的连通性，并且没有优先选择一个而不是另一个。

总结

这篇文章获得了2018年IEEE信号处理协会最佳年轻作者论文奖，斯坦福大学的美国工程院院士Goldsmith教授在引用本文时指出，该工作得到了图上带限信号的最优采样策略。本文将基础代数工具运用至图信号处理领域并给出了寻找optimal operator的贪心算法，在图信号处理的发展中起到了相当重要的作用。由于篇幅所限，在这里我们对部分内容进行了省略和缩写，大家感兴趣的话可以阅读原文，原文中在随机采样部分还有对Frames with Maximal Robustness to Erasures的讨论，同时也有不少图信号采样理论结合离散时间信号采样以及压缩感知等内容。

参考文献

[1]: Chen, Siheng, et al. "Discrete Signal Processing on Graphs: Sampling Theory. in IEEE transactions on signal processing 63.24 (2015): 6510-6523.

[2]: A. Anis, A. Gadde, and A. Ortega, “Towards a sampling theorem for signals on arbitrary graphs,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., May 2014, pp. 3864–3868.

[3]: E. J. Cande and J. Romberg, “Sparsity and incoherence in compressive sampling,” Inverse Problems, vol. 23, pp. 110–134, 2007.