现代信号处理教程（第三版）课件 第15 章 压缩感知的基础理论-1

第五篇压缩感知（CS）第15章压缩感知的基础理论第16章模拟/信息转换及CS的应用

第15章压缩感知的基础理论15.1压缩感知的基本概念15.2预备知识15.3信号的稀疏表示15.4测量矩阵需要满足的性质15.5可压缩信号的恢复15.6噪声情况下的信号恢复15.7测量矩阵的构造15.8稀疏信号恢复算法我们已迅速进入了数字化的信息时代：数字通讯数字控制数字化仪表数字家电数字化医疗仪器数字测量数字“图书馆”理论基础：数字信号处理（DSP）手机MP3、MP4数码相机录音笔U盘掌上电脑15.1压缩感知的基本概念

然而，物理世界的信息（信号和图像）是时间和空间的连续函数（模拟）。DSP能处理的是数字信号。将模拟信号和模拟图像转变为数字化的形式需要抽样，即模/数（A/D）转换。在数字信号处理中，经典的抽样定理，即Shannon抽样定理被誉为A/D转换的金标准。DSPA/D打开了由模拟世界进入数字世界的大门！

Shannon抽样定理：

设

是有限带宽的，抽样频率

至少要是其最高频率

的两倍，才能由抽样后的离散信号

精确地恢复（或重建）出

。如何重建？1.D/A；2.重建公式：

在实现信号和图像的A/D转换时，经典抽样定理限定的抽样频率过高，以致数字化后的数据量太大。如现代通信中，抽样频率可高达GHz；专业数码相机，几千万像素！4个小时的会议录音的数据量就是5Gbit。这给采集、存储、传输和处理带来了极大的负担！解决数据量大的问题，目前最通用的方法是数据压缩。采集－压缩过程有如下三个不足：（1）数据的长度

可能是非常大的；（2）变换后的小系数虽被舍弃，但要算出来；（3）大系数的位置也必须编码，这增加了运算

和存储的负担。JPEGMPEGMP3ZIP对模拟信号抽样，真的需要吗？

绝大部分物理信号有一个基本特点，即它们基本上是稀疏的（时域，特别是频域），或可压缩的，从而使得在低于Nyquist率下抽样变为可能。调幅信号频谱是稀疏的通信中的多带信号也都是稀疏的

我们能否直接“感知”信号

中重要的成分而对其采集、对不重要的成分不采集呢？这似乎是一个不切实际的想法，但它确实是压缩感知想要解决的问题。问题的关键是，如何由原来的关注最高频率转变为关注信号的“稀疏性”。DonohoD.L.认为经典的抽样定理是“错误”的，当然，它不是真正的错误，而是“心理”上的错误，即它促使人们在本来不用那么多数据的场合仍然想着要采集非常大量的数据。CS为新的信号抽样策略提供了理论基础，它用远小于Nyquist率的抽样频率对信号抽样，然后利用算法来对原信号进行准确，或近似恢复。这等效于将对信号的抽样和压缩合并为一步实现。CS能工作的基础是信号中存在的稀疏性。压缩感知压缩传感compressivesensingcompressedsensingcompressivesampling（压缩抽样）sparserecovery（稀疏恢复）”。CS定义15.1.1

如果向量

最多只有

个非零元素，

则称

是

稀疏的。所有

稀疏信号

的集合记为

，即

维

Euclidean空间等效：都表示

中非零元素的个数。显然，越小，中非零元素越少，越稀疏待“抽样”（重建）信号；未知，可能是模拟，可能是数字CS问题的描述：令：测量（已知）信号；它总是数字的。测量矩阵，长方阵目的：由测量重建出；测量“系统”，目的是由测量重建出；

欠定方程，未知数的个数大于方程的个数，因此有无穷多解。但如限制是稀疏的，则方程以大概率有唯一解。为唯一地求解

，必须对方程施加约束条件：目标函数解的名称subjectto令：最小平方解伪逆，基于范数最优解

最小

范数解等效于最小平方解，它测量的是信号的能量，着眼于信号整体的平方误差最小，因此，得到的解不具有稀疏性，无法用于稀疏信号的恢复。关于这一点，我们也可以这样来理解：由于

使用了

的所有列向量，因此，它以平均的方式包含了

的“整体”信息，这一结果倾向于平滑每一个列向量给出的贡献，因此得到的

不再是稀疏信号。

显然，一个合理的、自然的选择是利用范数。含意：在所有满足线性方程组

的解中，选择非零元素最少的一个作为我们需要恢复的

。

问题：

是稀疏的，但是，这个非零元素的位置是不知道的，有

个可能的分布，因此可有个满足不定方程。

因此，基于范数的求解是几乎不可能的，NP－Hard问题，组合最优化问题。NP：Non-DeterministicPolynomial（非确定多项式）为解决NP－Hard问题，人们提出了两个方法：一、基追踪（basispursuit，BP）

算法用取代：CS中的重要内容。二、贪婪（greedyalgorithms）算法

－正交匹配追踪：直接求，但不是

优化算法，而是迭代算法。对实际问题，在时域，或空域很少是稀疏的，但他们在时、空域具有相关性，因此经常需要考虑变换域的压缩感知：目的：由测量重建出；由做反变换得正交变换测量矩阵主要取决于

对信号的感知分两种情况，一是信号在时域（或空域）是稀疏的，那么对信号的测量也在时域（或空域）进行；二是信号在变换域是稀疏的，那么测量在变换域进行。总之，CS测量的是稀疏信号。且

被

看作已知的，而稀疏信号是靠优化算法求解出来的。“编码器（encoder）”又称“解码器（decoder）”又称表示映射CS的文献中记为问题可简洁地表为CS中的一些核心问题：什么条件下：？问题；什么条件下：？问题；什么条件下：？和等效问题；所有上述问题的回答，都取决于测量矩阵所具有的性质。

CS的一些特点：（1）由于

，因此CS对信号的测量是将信号的

采集和压缩结合在了一个步骤，避免了经典抽样需

要先采集、后压缩的分步实现。或者说，测量的数

据

只正比于压缩后数据的长度，它远小于原数

据的长度；（2）测量值

不是信号

本身，而是高维（

）信号

到低维（

）的投影，或者说，

的每一个值

都是

的所有值的组合；（3）测量是非自适应的，即测量矩阵

不随

而变化；（4）如果信号在传感器端的采集是昂贵的，费时的，

危险的，或不可能的，而在接收端的计算（即恢

复）是低廉和容易实现的，那么CS是特别有应

用价值的。模拟/信息转换的应用。（5）用低维的

来代替（或恢复）高维的

，这在

数字信号和数字图像的压缩、识别、稀疏表示及

重建等领域都有着广泛的应用。CS理论依赖于三个要求：（1）信号

，或其在变换域是稀疏的;（2）测量矩阵

要满足一定的性质；（3）高效的恢复算法。CS理论的主要内容：（1）信号的稀疏表示；（2）为保证唯一地由

恢复

稀疏信号

，？（3）测量矩阵

要满足的性质及其设计；（4）信号恢复的算法；（5）如何得到？A/I问题；（6）CS的应用。说明：CS希望解决对模拟信号以低抽样率抽样，并已取得了可喜的成果。但目前主流的CS的理论框架还主要针对离散信号。其原因：一是有利于应用经典的数学理论（矩阵和向量）；二是CS理论越发展和越完善，AIC距离实际应用也越近；三是在实际应用中我们也可以“直接”得到离散信号，如数码相机和CT图像。由于CS的理论框架目前主要是针对离散信号的，因此，除了模拟/信息转换这一最重要的应用领域以外，CS在针对数字信号和数字图像的领域也已经并正在获得广泛的应用，如医学成像、计算生物学、地球物理、人工智能、机器学习等。[Can06a]Candès.E.J.,Romberg.JandTao.T.Robustuncertaintyprinciples:exactsignalreconstructionfromhighlyincompletefrequencyinformation.IEEETrans.Inform.Theory,52(2):489–509,2006.[Don06]Donoho.D.L.Compressedsensing.IEEETrans.Inform.Theory,52(4):1289–1306,2006.两篇重要论文：被认为是CS的起源－2006DavidLDonoho教授：1957年生，现为斯坦福大学统计学系教授，2013年邵逸夫数学科学奖获得者。EmmanuelJ.Candès教授：1970年生，现为斯坦福大学数学、统计学、电工程学教授。TerenceTao（陶哲轩）教授：1975生。华裔澳籍数学家，UCLA教授。15.2预备知识

矩阵的零空间

矩阵的

向量的范数

凸优化与线性规划15.2.1矩阵的零空间（nullspace，NSP）NSP来自于线性方程组解的结构，考虑如下的线性方程组：该方程组的解有如下情况：（1）如果，满秩，有唯一解；（2）如果，满秩，齐次方程组只

有零解，即；

（3）如果，齐次方程组有基础解系，。

是线性无关的，且的所有其它解都可由其

线性组合来得到。

可看作一个空间的基，该空间就是矩阵

的零空间，记为

。（4）若，令，若

则有解；假定

是它的一个特解，

是

的一个元素，则

也是方程组的

解，当

取遍

中的所有元素时，我们就

得到方程组

的所有解。

注意：空间中的任一元素都使得，

因此，中的元素又称为矩阵的“化

零向量”。我们通常认为是行满秩的，因

此，的维数为。又称核空间：定义15.2.1：已知矩阵

，其零空间定义为已知矩阵

，其值域定义为显然例已知矩阵求的零空间维数和值域的维数，并讨论方程组

的解的形式。详细内容见教材

由15.1节的讨论可知，

，由得到。如果，基本的要求是

，

反之亦然。即我们要求映射和恢复是一对一的，这即是压缩感知中的唯一性问题。否则，我们将无法从重建出。令，如果，则化零向量，即线性方程组求解

矩阵零空间，目的：用到压缩感知

若保证映射和恢复的唯一性，

的零空间一定要具有一定的性质。下面给出的是最基本的一个。定义15.2.2矩阵

被称为具有

阶零空间性质（nullspaceproperty，NSP），如果式中表示空间，因为，由此该式的含义是

的零空间中不包含

稀疏的向量。它又可表为即

的零空间和

稀疏向量的集合没有交集之所以说定义15.2.2是矩阵零空间性质中最基本的一个，是因为在压缩感知中还要考虑“半稀疏（semi-sparse）信号的压缩问题。所谓半稀疏信号，是指对

，它有个元素的绝对值起到主导作用（即较大）。但其它个元素并非全部为零，而是有很小的值。这一类信号又称可压缩信号，它也可以看作稀疏信号被噪声污染后形成的。因此，对这一类信号的恢复问题，零空间性质的要求要严一些。粗略地说，在的零空间中除了要不包含稀疏及稀疏的向量外，还要不包含极易压缩的向量。定义15.2.3即是针对这一类信号的恢复问题而提出的。定义15.2.3矩阵

被称为具有常数

的

阶零空间性质，如果对

的任意化零向量

和任意满足

的下标集合都成立。符号说明：下标集合

的补向量和在由指定的位置上的元素相同，而其余的元素（由

指定）是零；同理，矩阵

是矩阵

的子矩阵，其列是由

指定的

的列。

例如：如果，仍存在常数

使上述定义成立，则说具有阶NSP性质。另外，NSP的定义不唯一，如说明：CS是近十年来新发展的学科领域，因此一些定义和定理在文献中的描述还没有统一。

NSP实际上是对矩阵

的零空间中向量的元素的分布提出了要求，即它的非零元素不能集中分布在一个小的子集中。

结论：满足

阶零空间性质的向量

的非零元素的个数应大于

，而且不小于。等效说，如果

满足零空间性质，那么，在其零空间

中唯一的

稀疏向量应是

。矩阵的NSP在CS中有着重要的应用

由式（15.2.3）的

阶零空间性质可以想到，因为

，那么

的列向量中一定有若干列是线性相关的。为了避免

的情况出现，除了要求其零空间中不包含

稀疏及

稀疏的向量外，还要对其线性相关的列数给以控制。这就是下面要讨论的矩阵

。

矩阵的

又称为矩阵的

稀疏度

。15.2.2矩阵的

定义15.2.4

矩阵

的

是其最小的

线性相关的列数，记为

。上界和下界含意：在矩阵

所有的列中，最少可以找出多少列

使其满足线性相关性。这里之所以考虑“最

小”，是因为向量越多越容易满足线性相关。矩阵的秩和spark都用来描述矩阵的基本特征，但二者有明显的不同。矩阵的秩是其最大线性无关的列数，而spark是其最小线性相关的列数，一个是“最大”，一个是“最小”，一个是“线性无关”，一个是“线性相关”。另外，对

矩阵，求出其秩的方法是通过初等变换将其转换为一个阶梯矩阵，其不等于零的行就是它的秩，这是一个“顺序”的计算的过程，计算复杂性为

。而求解其spark是一个组合过程，计算复杂性为

。由式（15.2.6）可知，若

的

越大，那么其

也越大，这就是说，

的线性无关的列数就越多。这样，将映射为，保留的

的信息越多，结果是越有利于由

准确重建

。因此矩阵的

是描述矩阵的一个重要参数。在后面的讨论中，它和NSP一样都要反复用到。15.2.3向量的范数时，“真范数”真范数满足左边四个性质

时的范数有其用处，但不再满足上述四个关系，因此，

这时的范数称为“准范数quasinorm）”，应用最多的是

时的范数

：包含了非零元素个数的三个表达方式表示的“势（cardinality）”范数的单位球（unitball）:

的单位球是和坐标轴重合的十字架（不包括原点）

的单位球是菱形，其顶点在坐标轴上

的单位球是一个圆，圆心在原点

时的单位球是内凹的

时的单位球是外凸的向量范数单位球的形态：有什么用处？假定：，稀疏。含意？假定得到的一个近似，考查，在下，近似性能

应位于二维平面的直线上那种情况近似好？再考虑：，含意？

范数可给出全局最优解，

但给不出稀疏解；

范数能给出稀疏解；

的解的几何分布：

是个超平面的交集，

维数为，记为转化零空间（translatednull～）仿射空间（affine～）二者有相同的

，

不同的。前者最稀疏！

范数球的位置：

范数可以提升信号的稀疏性，其求解又等效于凸优化问题。在CS起到了非常重要的作用。15.2.4凸优化与线性规划线性规划问题的数学描述：目标函数约束条件:变量满足右式的称为“可行点”，其集合称为“可行域”。

并非所有的连续可微函数都有最优解，即使有，也不一定唯一。然而，如果上式的目标函数是凸函数，而且可行域也是凸集，则上式的优化问题的任何最优解必然是全局最优解。另外，对于凸集上的凸函数的最优化，存在唯一的全局最优解。因此，凸集与凸函数在最优化的理论中有着重要的作用。一个可行点若满足则称

为上面优化问题的全局最优解定义15.2.5设

为

中的一个集合，如果对

内的任意两点

，联结它们之间的线段仍然属于

，则称

为一个凸集。即凸集非凸集

凸优化的最优解应该位于凸集的顶点。由于可行域非空的线性规划就是一个凸规划，因此可得出有关线性规划最优解的结论，即（1）如果线性规划问题有最优解，那么最优解在可行域的顶点中确定；（2）如果可行域有界、且可行域只有有限个顶点，则最优解存在，并且只需在这有限个顶点中确定。

线性规划问题的求解有着很长的历史，经典的方法是由Dantzig.G.B在1947年提出的单纯形法（simplexmethod）和由Karmarkar于1984年提出的内点法（interiorpointmethod）。15.3信号的稀疏表示稀疏表示：用高效的算法在保持信号信息不变的情况下最大可能的降低信号的维数，这是对信号建立最佳稀疏模型问题。文献认为信号的稀疏模型是“奥卡姆剃刀（Occam'sRazor）”问题的又一个例子，即面对一个信号的多种表达方式，最简单的一种即是最好的选择。15.3.1稀疏信号及可压缩信号

我们希望信号越稀疏越好，这有利于信号的压缩、存储、特征提取及应用。

维向量（信号）如果只有个非零元素，则称是稀疏的，记做记为非线性模型中的子空间非线性空间：

个子空间的并集

如果信号不是稀疏的，但如果可以由一个稀疏信号很好的近似，则称该信号是可压缩的。

范数下的最佳

稀疏近似误差为显然，若取了的个最大元素，而其余元素为零，则，称为的“最佳项近似”。定义15.3.1

将正交变换系数排序：

，

，如果系数满足

，则称是可压缩的。15.3.2信号稀疏表示的基本方法信号在时域和空域一般是非稀疏的，但物理信号具有很强的相关性，因此，在变换域（如频域）通常是稀疏的。之前，人们习惯用的是正交变换：：正交矩阵DFT（离散傅里叶变换）DCT（离散余弦变换）DWT（离散小波变换）正交变换的优点：去除信号中的相关性；将信号能量浓缩到少数系数上；计算简单“优雅(elegance）”的变换，JPEG，MPEG，正交变换的不足：当信号中包含多种模式时，利用单一的正交基不能很好地“匹配”所要分解的信号，因此也不能有效地实现信号的稀疏表示。

例如，DFT对谐波信号、均匀平滑的信号非常有效，但是当信号中存在有间断点和尖脉冲时，傅里叶变换的效果就不理想，无法得到好的稀疏表示。说明单独的一个正交基不能同时匹配两种不同类型的信号。再例如，一幅图像有平滑的区域，也有剧烈的边缘。小波变换在表示具有有限断点的平滑分段连续信号方面是最优的，对具有复杂纹理结构的图像也具有很强的优势，但由于图像的边缘具有不连续性，并且是按空间分布的，因此，小波在处理图像边缘方面的效果不理想。对含有多种模式的信号，应该用多个“基函数”构成一个混合的“基”来自适应信号的特征，以匹配信号中的不同模式，并取得最佳的稀疏效果。该混合的“基”称为“字典（dictionary）”。向量，“原子”变换矩阵，长方阵已知信号

待求稀疏信号未知数大于已知数，欠定问题，无穷多解有唯一解，“NP”难，“匹配追踪”变换矩阵“基追踪”算法重大进展稀疏表达和压缩感知类似。一个问题的两个方面：已知信号

待求稀疏信号