第1章 稀疏信号模型
压缩感知（compressive sensing），在信号处理领域也称为压缩采样（compressive sampling），是与传统的信号采样方法不同的信号采样模式，它可以用远比传统方法少的样本或测量值恢复信号，从而降低采样频率和数据量。要使压缩采样成为可能，必须有两个前提条件，一是信号的稀疏性（sparsity），二是信号采样模式的非相干性（incoherence）。信号的稀疏性是指一个信号在适当的变换基下具有简洁的表示，也就是说它是可压缩或稀疏的。自然界中有很多信号都具有稀疏性。非相干性是对信号的时域和频域表示的对偶性的扩展，表明在变换基下稀疏的信号在获取该信号的域中是广泛分布的。
信号处理方法或算法大多是专注于物理系统产生的信号。许多自然和人造系统可以建模为线性系统。因此，下面首先考虑具有线性结构的信号模型。在现代信号处理中，通常将信号建模为在某个向量空间中的向量。向量空间的理论和概念也是压缩感知理论的基础。
1.1 向量空间
向量空间描述了我们常常需要的线性结构，比如说，如果把两个信号加在一起，那么我们就得到一个新的、物理上有意义的信号。在向量空间中，我们可以应用来自空间几何中的直觉知识和工具，如长度、距离和角度，来描述和比较我们感兴趣的信号。即使信号是在高维或无限维空间中，这种方法也是非常有用的。
1.1.1 赋范向量空间
通常把信号看作实值函数，其定义域是连续或离散的，无限或有限的。我们主要关注定义了向量范数的向量空间，称为赋范向量空间（normed vector spaces）。
在现代信号处理中，常用范数度量信号强度或误差大小。考虑定义域为离散有限的信号，它们可以看作n维欧几里得空间中的向量。在空间中，向量的范数定义为[1]
（1.1）
上述范数满足三角不等式。当时，范数定义为向量元素绝对值的*大值，即。在欧几里得空间中，向量和的内积定义为[1]
（1.2）
利用内积的定义，范数可以表示为。
在某些应用场合，将范数的定义扩展到p＜1是有用的。不过，当p＜1时，按照式（1.1）定义的不再是范数，而是拟范数（quasinorm），因为它不满足三角不等式。用记号表示信号x的支撑（support），，则表示x的基数（cardinality）。注意，既不是范数，也不是拟范数。
p取不同的值，范数（包括拟范数）具有明显不同的性质。例如，在中不同范数或拟范数表示的单位球，如图1.1所示。
1.1.2 向量空间中的基和框架
如果集合中的所有向量能张成（span）欧几里得空间，并且这些向量是线性独立的，则称为中的一组基（basis）[1]。空间中的每一个向量都可以唯一地表示为这组基的线性组合。具体来说，对于向量，存在唯一的一组系数使得。用表示n×n矩阵，它的列由组成，表示长度为n的向量，则向量可以表示为紧凑形式：。
规范正交基（orthonormal basis）是一类特殊的基向量，它们满足正交性，即如果满足：
（1.3）
利用正交基的特性，很容易计算系数：，或表示成矩阵形式：
（1.4）
由于矩阵的列具有正交性，因此，，这里I表示n×n单位矩阵。
将基的概念推广到可能线性相关的向量集合，就产生所谓的框架（frame）[1，2]。准确地说，框架是空间中与矩阵对应的一组向量，d＜n，并且对于向量，满足：
（1.5）
其中。注意，A＞0意味着矩阵的行必然是线性独立的。在保证不等式成立的条件下，若A取可能的*大值，B取*小值，则称它们为*优框架边界。如果可以选择A和B相等，则称为A-紧（A-tight）框架。如果A=B=1，则称为帕塞瓦尔框架（Parseval frame）。如果存在某个，使得，则称为等范数框架。若?=1，则称为单位范数框架。另外，在框架是d×n矩阵的情况下，A和B分别对应矩阵的*小和*大特征值。
框架的冗余性使得它们可以提供更丰富的数据表示[3]。对于给定的信号x，存在无穷多个系数向量c，满足。为了获得一组可实现的系数，可以采用对偶框架（dual frame）。任何满足下列关系的框架称为可选对偶框架。
（1.6）
特别地，称为典范对偶框架（canonical dual frame），也称为穆尔-彭罗斯伪逆（Moore-Penrosepseudoinverse）。值得注意的是，由于要求矩阵的行是线性独立的，保证了是可逆的，也就是说，是定义明确的（well-defined）。由此，可以得到一组可实现的系数如下[1]：
（1.7）
需要指出的是，在稀疏逼近（sparseapproximation）的文献中，基或框架分别被称为字典（dictionary）或过完备字典（overcomplete dictionary），字典元素被称为原子（atoms）。
1.2 低维信号模型
信号处理的核心是从不同类型的信号或数据中获取、处理和提取信息的高效算法。为了针对特定问题设计信号处理的算法，必须对感兴趣的信号建立精确的模型。这些模型可以采取生成模型、确定性类或概率贝叶斯模型的形式。许多经典信号处理方法是将信号建模为向量空间（或子空间）中的向量，简单的线性模型往往无法捕捉许多常见的各类信号中存在的大部分结构，尽管将信号建模为向量是合理的，但在许多情况下，空间中并非所有可能的向量都代表有效信号。为了应对这些挑战，近年来，许多领域对各种低维信号模型的兴趣激增。本节简要介绍压缩感知领域中*常见的低维结构。首先考虑有限维信号的传统稀疏模型，然后讨论将这些模型推广到无限维（连续时间）信号，*后简要介绍低秩矩阵（low-rank matrix）、流形（manifold）和参数（parametric）模型。
1.2.1 稀疏模型
一般来说，信号可以用已知基或字典的几个元素的线性组合很好地逼近。如果这种表示是精确的，则信号是稀疏的。稀疏信号模型提供了一个数学框架。
1.稀疏性和非线性逼近
定义：对于信号x，如果它*多有k个非零值，即，则称x是k-稀疏的。用记号表示所有k-稀疏的信号集合[1]。
通常遇到的信号x本身不是k-稀疏的，而是在某个基上具有稀疏表示，此时仍然称x是k-稀疏的，但要理解为，。在信号处理和逼近理论中利用稀疏性实现数据压缩、去噪等任务[4，5]，也是机器学习理论中避免过拟合的方法[6]。
2.稀疏信号的几何意义
稀疏信号模型是一种高度非线性的模型，因为选择使用哪种字典元素会因信号而异[4]。通过观察可以看出，两个k-稀疏信号的线性组合通常不再是k-稀疏的，因为它们的支撑可能不一致。也就是说，对于任何，不一定有，但可以肯定的是，x+z一定是2k-稀疏的，即。稀疏信号集合并不构成线性空间，相反，它包括所有可能的个典范子空间的并集。
3.可压缩信号
在实际应用中，大多数信号都不是真正稀疏的，但它们是可压缩的，因此可以用稀疏信号很好地逼近它们。在不同的应用场合，这样的信号被称为可压缩的、近似稀疏的或相对稀疏的。用稀疏信号逼近可压缩信号可能产生误差，通过计算信号逼近误差可量化压缩率。
（1.8）
显然，如果，则对任意的p，有。
从另一角度来讨论可压缩信号，考虑它们系数的衰减速率。实际上，对于许多重要的信号，存在某个基使它们的系数服从幂律衰减。在这种情况下，信号是高度可压缩的。设信号x可表示为：，将其系数从大到小进行排序，即。如果存在常数C1，q＞0，使得，则称信号x的系数服从幂律衰减。q越大，系数幅度衰减越快，信号的可压缩性就越强。由于系数幅度衰减非常快，可以用个系数准确表示可压缩信号。
1.2.2 信号子空间模型
1.子空间的有限联合
在某些应用中，信号的结构不能仅用稀疏性来完全表达。例如，当信号中只允许某些稀疏支撑模式时，可以利用这些约束来表示更简洁的信号模型。具有代表性的例子很多，这里略举两例：①对于分段平滑的信号和图像，小波变换中的主导系数倾向于聚集成小波父子二叉树内的连通根子树[7]。②在某些情况下，稀疏信号的少数分量不是对应于向量（即矩阵的列），而是对应于特定子空间中的已知点。如果通过连接这些子空间的基来构造一个框架，信号表示的非零系数在已知位置形成块结构[8-10]。对于具有这种附加结构的k-稀疏信号，可以通过将信号的可行支撑限制为可选择的个非零系数的一个小子集来捕获这种结构。这些模型通常被称为结构化稀疏模型[7，11，12]。在非零系数聚集成簇的情况下，结构可以用子空间的稀疏并集来表示[7，10]。结构化稀疏和子空间联合模型将稀疏的概念扩展到更广泛的信号类别，可以表示有限维和无限维信号。
标准稀疏信号的并集是由标准的子空间组成的，这些子空间与空间n个坐标轴中的k个对齐。选择更一般的子空间，其表示能力强大，可以适应许多有趣的信号先验（signal priors）。具体地说，已知信号x位于M个可能子空间的某一个子空间，则x一定位于M个子空间的并集中[10，12]。在一般的稀疏场合中，子空间联合模型是非线性的，来自并集的两个信号之和通常不再在中。信号集合的这种非线性特性使得任何信号处理都更加复杂。因此，这里主要考察一些特定的联合模型，例如，结构化稀疏支撑，由满足支撑附加限制的稀疏向量组成（即向量非零项的索引集），只有中个子空间中的某些子空间满足要求[11]。还有，子空间的稀疏并集，构成该并集的每个子空间是k个低维子空间的直和[10]。
2.用于模拟信号模型的子空间联合
压缩感知的主要目的之一是设计新的感知系统来获取模拟信号。相反，上述有限维稀疏信号模型假设信号是离散的。在某些情况下，使用中间的离散表示将上述模型扩展到连续时间信号是有可能的。例如，一个带限的周期性信号可以用一个有限长度的向量来完美地表示，该向量由奈奎斯特速率采样的样本组成。然而，通常更好的方法是将稀疏性的概念进行扩展，为模拟信号建立子空间联合模型[13-15]。一般来说，当处理模拟信号的子空间联合模型时，需要考虑三种情况，即无限维空间的有限联合、有限维空间的无限联合和无限维空间的无限联合。
在上述三种情况中，每一种情况都至少有一个部分可以取无限值，也就是维度无限和联合无限。我们要讨论的模拟信号结果就是这样的：要么底层子空间是无限维的，要么子空间的数量是无限维的。模拟信号可以表示为子空间的联合，这样的很多例子都是众所周知的。例如，属于无限维空间的有限联合的一类重要信号是多频带模型（multiband model）[14]。在该模型中，模拟信号由带限信号的有限和组成，信号分量通常具有相对较小的带宽，但分布在相对较大的频率范围[16-19]，这类信号的亚奈奎斯特（sub-Nyquist）恢复技术可参考本章文献[18]、文献[20]和文献[21]。另外，新息率（rate of innovation）有限的信号，也是可以表示为子空间联合的一类信号[13，22]。该模型可用于描述具有少量自由度的许多常见信号，它对应于有限维子空间的无限联合还是有限联合，取决于具体的结构[23，24]。在这种情况下，参数的可能取值集合是无限维的，每个子空间对应于参数值的某种选择，因此，模型所张成的子空间的数目也是无限的。*终的目标是利用可用的结构来降低采样率。
1.2.3 低秩矩阵模型
与稀疏性密切相关的另一种模型是低秩矩阵模型[1]：
（1.9）
也就是说，集合由秩小于等于r的所有矩阵M构成，即，其中为非零奇异值，是相应的奇异向量。这里并非限制用于构造信号的矩阵数目，而是对非零奇异值的数目进行约束。通过计算奇异值分解中自由参数的数量，可以很容易地观察到集合具有个自由度。当r很小时，这一数值远小于矩阵元素的数目。在多种实际应用场景中都会出现低秩矩阵，例如，低秩汉克尔（Hankel）矩阵对应于低阶线性、时不变系统[25]。在许多数据嵌入问题中，如传感器定位，传感器之间的距离矩阵通常秩为2或3[26，27]。*后，近似的低秩矩阵自然出现在协同过滤（collab
展开
