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

第五篇压缩感知（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”难，“匹配追踪”变换矩阵“基追踪”算法重大进展稀疏表达和压缩感知类似。一个问题的两个方面：已知信号

待求稀疏信号

变换矩阵，

待重建高维信号已知信号

测量矩阵，欠定；NP-Hard；长方阵：基追踪；匹配追踪压缩感知

稀疏恢复（sparserecovery）

权威期刊ProceedingsoftheIEEEvol.98，No.6，2010专辑：ApplicationsofSparseRepresentationandCompressiveSensing

把稀疏表示和压缩感知合在一起进行讨论字典应具有的功能定位功能；多分辨率功能；自适应功能；几何不变性和过完备功能。解析字典Curvelets变换Contourlets变换Bandelets变换学习字典MethodofOptimalDirections；UnionofOrthobases；GeneralizedPCA；K-SVDAlgorithm。如何从

中选最优的

个原子。稀疏表达两个核心问题如何设计最优字典

；（1）信号的稀疏表示；（2）对

稀疏信号，测量数

的最小值，即

取多少才能保证唯一地由

恢复出

？（3）测量矩阵

应具有的性质及

的设计；

（4）信号恢复的算法（基追踪，正交匹配追踪）；（5）如何得到测量

？（6）CS的应用。CS的核心内容

CS的应用：

模拟/信息转换，A/IC（1）随机解调（RD）

；（2）调制宽带转换器（MWC）；（3）Xampling已提出的方案CS可应用于一切需要由某些线性测量的结果来重建信号和图像的领域，特别是当完备的测量的获得是昂贵的，长时间的，困难的，危险的，或者是不可能的场合。如CT，MRICS和A/IC的理论正在发展中！CS的其他应用领域：图像压缩；医学成像；计算生物学；地球物理；超光谱成像（hyperspectralimaging）；压缩雷达成像；天文学、通信、遥感；计算机工程；表面计量学（surfacemetrology）等稀疏表达在生物医学工程中的应用医学图像图像压缩；图像去噪；图像识别；图像修复；图像编码；应用最多的：MRI，超声，CT，面部识别医学信号盲源分离；脑电中癫痫特征波的检测；诱发脑电提取；脑电的源定位；心电特征（P，R，T）检测。

15.4测量矩阵需要满足的性质

的NSP约束等距性质（RIP）相干性（coherence）（1）是准确稀疏的；（2）测量过程不存在噪声；本节讨论的是：

矩阵的NSP不好应用，spark的求出是一组合问题，也不好应用。此外，在存在噪声的情况下，由NSP和spark给出的重建往往缺乏鲁棒性，为此，人们又提出了一些新的参数：最著名的是矩阵的约束等距性质（restrictedisometryproperty，RIP）及相干性。15.4.1

测量矩阵的约束等距性质定义15.4.1

令整数

对所有的

稀疏信号

，等距常数

是满足的最小标量，如果，则称满足

阶的RIP并具有等距常数

。RIP的概念最初由EmmanuelJ.Candès和TerenceTao在文献[Can06b]中提出，当时称为均匀不定原理(uniformuncertaintyprinciple，UUP)，后来文献[Can05]将其重新定义为RIP。（1）定义要求对所有的

都成立，在

维空间中有

个这样的

。当然，实际待求的只有一个。（2）不严谨地说，若

不太接近于1，则称

RIP

粗略地看，（15.4.1a）式定义的RIP是想保证

和测量的能量没有太大的差距。现对RIP给出更多的解释。（3）如果保范变换？但现在

是扁的长方阵，隐含意思是：从

中任取

列所形成的

子矩阵应该接近于正交阵。显然

越小，该子矩阵接近正交阵的程度越好。因此，当

投影到

的行向量上后，具有RIP性质的

就近似地保护了它的Euclidean范数

（或能量）。上述结论又意味着

稀疏信号不会落在

的零空间。这一点很重要，否则无法恢复该稀疏信号。为强调该子矩阵，RIP又可定义：

（4）：方阵，称为Gram矩阵。若满足RIP，

则

正定，对，则该矩阵的特征值

位于之间。（5）RIP定义的另一含意：如果

满足

阶的RIP，

则定义近似保护了任意两个

稀疏向量之间的距离。如果：

：

是指下标集合的势

时仍满足RIP定义的最小常数。

的取值也应该在

之间。这时，我们说

具有

阶的RIP性质。类似的，我们还可以定义

，

等。（6）如果

满足

阶的RIP并具有等距常数

，那

么，对任意的

，

，自动地具有

阶

的RIP性质并具有等距常数

。（7）如果

“感知”的是变换系数

，那么RIP定义

中的矩阵

应该换为矩阵

。这时，

具有

阶的RIP。（8）将RIP的定义和标架的定义相比较，会二者有非常相

似之处。它们都给出了信号

在通过非正交阵

变换前后能量的约束关系。

上面8个解释说明：测量矩阵

的RIP性质保证了通过变换

前后信号的能量及几何结构基本保持不变，同时也保护了两个

稀疏信号在变换前后的距离，从而使得

稀疏信号的准确恢复成为可能，也保证了恢复的稳定性。为了求得稀疏信号的准确恢复，人们希望在尽可能小的测量数目

的情况下，寻求具有较小的等距常数

和较大稀疏度

的测量矩阵

。15.4.2测量矩阵的相干性定义15.4.2测量矩阵

的相干性定义为将的列归一化越小，中不相关（或独立）的列越多，中保留的信息越多，越有利于的恢复。因此，在构造时，希望它具有尽量小的相干性。下面的定理给出了的NSP，spark，相干性之间的关系，也给出了测量数

的约束。定理15.4.1如果

满足

阶的RIP并具有等距常数

，则

具有

阶零空间

性质，且RIP常数证明见教材，用到两个引理。定理说明：如果矩阵

满足

阶的RIP，则它也同时满足

阶的NSP。RIP给出了比NSP更为严格的条件，可以用来考虑存在噪声情况下信号的恢复。

引理

假定

，则

稀疏信号三个范数之关系定理15.4.2对

，下面的关系成立

至少有列线性相关满足spark定义定理15.4.3对任意的

，其相干性和spark

有如下关系该式给出了一个重要的关系，即

的相干性越小，其spark越大，

线性无关的列向量越多，由这些列构成的

的子矩阵越接近于正交。这正是我们所希望的。定理15.4.4记

的相干性为

，假定其每一列的

范数都归一化为1，则对所有的

，

具有

阶RIP并具有等距常数：测量矩阵和正交矩阵之间的互相干性也有着重要的应用，列的范数归一化后，其定义为：测量两个矩阵之间的最大相关性15.4.3解唯一性的条件

解唯一性：即

最小，或如何保证

？直观理解：希望：对两个不同的：必须有：因为：结论：否则无法恢复：将出现：含意？

该式又可简单的解释为：为保证解的唯一性，矩阵

的零空间中必不包含稀疏的向量。解的唯一性，有多种描述方式，如定理15.4.5

对任意的

和

，当且仅当

时，测量系统

有唯一解

。

该定理的一个等效说法是:如果

的任意

列都是线性无关的，那么，任意

稀疏信号

都可以唯一地由

来恢复。由于：的行秩是，由定理，必须有此结论很重要，指出，为恢复出稀疏信号，测量数的长度不能小于。定理15.4.6对任意的

，如保证

，

则下述说法等效：（1）对所有

，存在一

，使得

；

（2）：是正定矩阵；（3）；（4）对任意具有

的下标集合

，矩阵

的秩为

；定理15.4.7对任意的

和，如果

其解

满足如下关系则测量系统

有唯一解

。对一个给定的感知矩阵

，该式给出了所能感知的信号稀疏水平的上限。定理15.4.8如果

满足阶RIP，且

，则对所有

，有定理15.4.8是直观的：因为如果

，由RIP的定义，

将有

列线性相关，则存在一

使

。令

，有

，那么

就不是唯一解。15.4.4解唯一性的条件定理15.4.9如果

满足阶RIP，且

，，则对所有

，有对比定理15.4.8和15.4.9可以看出：

保证

保证结论合理：利用

范数来代替

范数是放宽了最优化的条件，当然对测量矩阵的要求要变得严一些。要求要求其实：可看作和等效的条件

解的唯一性也可用NSP给出：定理15.4.10给定

，当且仅当满足

阶零空间性质时，任意稀疏向量

都是唯一最小范数解。

实际信号在时域多不是稀疏的，而经正交矩阵变换后多是稀疏的，因此，研究测量矩阵

应具有的性质同样是重要的。对该问题，用的最多的是互相干

。下面的定理给出了

和测量数

之间的关系以及保证

解唯一性的条件。定理15.4.11假定信号

在正交基

下的变换系数

是

稀疏的，且

是对

的均匀和

随机测量，如果保证则优化问题以大概率有准确解。显然，越小，需要的越少。若则以的测量可恢复长度为的。文献指出:RIP等效于要求

的行向量

不能由

的列向量

线性表出，反之亦然。

随机矩阵15.4.5和解等效的条件前面已指出：是、等效的条件定理15.4.12令

是一行满秩矩阵，如

果一个解

存在并满足则是

和

问题的唯一解。15.4.6测量边界前面指出，为保证

解唯一性，测量数不能小

。定理15.4.10通过互相干

给出了

和

的关系。

在CS的文献中

又称为测量边界。定理15.4.13若

满足

阶RIP并

，则

更一般关系定理15.4.5～15.4.13给出了

，

唯一、等效条件及和的NSP、spark、RIP和之间的关系。很重要15.4.7关于

解唯一性的进一步说明

由于CS是近十年来新发展起来的领域，理论的发展有一个不断完善的过程，因此定理15.4.5～15.4.13所描述的内容及NSP的定义在文献上不尽相同，特别是唯一性的条件的表述，如：文献[Can05]：文献[Can06c]：文献[Can08b]：文献[Fou09]：[Cai10]：15.4节的公式和结论都较多，现总结如下：（15.4.11b）（15.4.9）需要指出：上面讨论的各个定理都是针对

是准确稀疏信号和无测量噪声情况下的结论，在不是稀疏信号和存在测量噪声情况下的信号恢复问题是下面两小节要讨论的内容。

15.5可压缩信号的恢复以上讨论，假定，这是理想的信号模型。实际信号多是近似稀疏，或可压缩的。因此，研究可压缩信号的CS更有意义。对可压缩信号近似误差将中最大个元素按大小排在前面，并赋予，再令其它元素为零。最佳项近似对非准确稀疏的可压缩信号：，近似程度？特别关心和最佳项近似误差的关系：重点关心如下关系：（1）.若是稀疏的，则左边＝0，无误差恢复；（2）.否则，则左边的误差和右边的最佳项近

似误差建立了联系。（A）定理15.5.1令

表示

的任一解码算

法，如果

和

满足（A）式，则

满足

阶NSP。反之，如果满足

阶NSP，则（A）式的近似误差关系成立。因此满足

阶NSP是（A）式成立的充要条件。上述讨论的是任一解码算法，更关心定理15.5.2令

是

解，对

，如果

满足

阶的RIP且

，则下面两式成立该定理是CS中一个重要和著名的定理，由Candès在08年提出并给出证明。文献[Bar13]又给出较详细的证明。

15.6噪声情况下的信号恢复

矩阵

对

测量时，会存在误差：可能来于传感器，或舍入误差和量化误差。这时，“感知”模型变成误差向量记在有噪声情况下，关心近似程度定义15.6.1令:，,，若则称编码－解码对是C－稳定的。该定义说明一简单事实，即测量误差在恢复过程中其影响不会任意大，它将不超过误差自身的

范数。

定理15.6.1如果:是C－

稳定的，则

对所有的

，下述关系成立RIP和C－稳定的关系定理15.6.2如果

满足

阶的RIP且

，令

及

，再令

是满足的最优解，则式中近似误差无噪声时信号恢复的误差噪声引起，正比于噪声能量的含意：15.7测量矩阵的构造用于：

稀疏信号；

可压缩信号；

含噪信号准确、近似准确恢复性能描述：NSPsparkRIP，

要满足定理15.4.5－15.4.13所提要求。小的RIP常数和相干性，大的spark。但这些性能的测量比较困难：满足RIP？需要考察由于非零元素位置不同而可能有的

个

稀疏信号

是否都满足RIP定义。研究发现，如果

是随机矩阵，则以大概率有RIP性质。15.7.1Johnson–L引理和浓缩测量的概念15.7.2随机测量矩阵（1）高斯测量矩阵每一个元素都是高斯分布，且I.I.D（2）伯努利测量矩阵或者可以用浓缩不等式证明，高斯和伯努利矩阵以大概率具有RIP性质。（3）亚高斯（subgaussian）测量矩阵

：高斯分布

：亚高斯分布

亚高斯种类很多，在一定的条件下，高斯分布、伯努利分布和均匀分布都可以看作是亚高斯分布：（1）（3）零均值，且常数，（2）：亚高斯分布伯努利分布全部由亚高斯随机变量组成的矩阵成为亚高斯矩阵。定理15.7.2令

是亚高斯随机矩阵，则

的RIP常数以至少

的概率满足

，且：常数，只和亚高斯参数

和

有关给出了类似15.4.7节讨论过的边界条件。另外，如果是亚高斯矩阵，不管正交阵如何选择，还是亚高斯阵。15.7.3部分随机傅里叶矩阵

虽然随机测量矩阵都具有RIP性质，且可达到测量下界，但有不足：（1）当需要对测量矩阵提出各种制约时，因为它们是随机的，能给出的自由度很小，因此制约常无法实现；（2）随机矩阵的每一个元素都要存储，因此在硬件实现时困难；（3）缺少矩阵和向量乘的快速算法，限制了恢复算法的速度。DFT矩阵，确定性：

在DFT阵中随机且均匀选择

行，构成

的测量矩阵

。显然，它具有部分随机性，称为部分随机傅里叶矩阵。其一个突出优点是可用FFT来计算矩阵和向量的乘，提高编码和解码速度。

似傅里叶随机矩阵的构成，也可以利用一般的正交矩阵来构成结构随机矩阵。又称为一般正交集总。定理15.7.23令

是部分随机傅里叶矩阵，则

的RIP常数以至少

的概率足

，且，均为常数15.7.4确定性测量矩阵

虽然随机矩阵可以大概率满足RIP条件，但由于其存储量大、缺乏快速算法等不足，特别是通过硬件实现时产生随机数较为困难，因此人们在工程实际中更希望能使用确定性测量矩阵。文献报告了该方面的一些进展，但离实际应用还很远。研究出既能满足RIP条件，又能接近于最佳的

确定性测量矩阵仍然是一个待解决的问题。15.8稀疏信号恢复算法欠定方程，无穷多解。如限定是稀疏的，则方程以大概率有唯一解。如何求解？基追踪：问题；贪婪算法（匹配追踪）：15.8.1基追踪（basispursuit，BP）

基追踪实际上不是一个算法，而是一个最优化的原理。其基本思想是找到一个信号的表示，使其表示系数