压缩感知的英文名字是compressed sensing （也可以称为compressive sensing简称CS）。CS 属于数学领域的内容，谈到CS的工程应用领域主要为：1）Magnetic Resonance Image2）Synthetic Aperture Radar3）Wideband spectral Sensing香农/那奎斯特采样定理告诉我们，对一个带限信号采样时，要想使得我们采样得到的信号 具有和原始带限信号的信息完全一样，也就是可以利用我们的采样得到信号去重建我们的信 号时，对采样速率的限制要求是必须至少达到原始带限信号的频带的2倍。在大多数应用中， 例如在数字图像和视频摄等应用中，那奎斯特率会很大，从而我们会有非常多的样本，为了 将我们得到的大量的样本存储，传输，我们通常会对这些采样得到的数据进行压缩。另外， 在其他诸如成像系统如医学图像扫描仪，雷达等，高速AD转换器等的领域中，如果将我 们的信号采样率提高到超过现在最先进的水平，其花费是巨大的。在本讲中我们将会学到一种全新的采样工具去避免上述的问题中的高采样率问题。该工具是 2006年由Donoho和Candes, Romberg, and Tao首次提出的compressed sensing。现在我们利 用这一很年轻的采样工具去代替传统的采样重建的那奎斯特问题。为了实现对某些类型（压 缩感知的使用的前提是我们的信号是稀疏的（sparse）的信号能实现低于那奎斯特率的采 样获得我们的信号（并可以运用这个信号去重建我们的原始的信号），压缩感知工具利用更 一般的线性度量方案（more general linear measurement scheme ），并融合最优化的 技术（ an optimization ）。我们要采样的的信号，能够进行压缩感知技术的前提就是该信号是稀疏的，也就是利用 信号的可压缩性（compressibility），从而实现减少我们的采样的样本数目，且可以重 建我们的原始信号。压缩感知与普通的采样率的一个不同之处就是，我们测量的不再是信号的某一采样点的 数据，而是一组更加一般的线性方程去描述信号。现在考虑一个实值，离散，有限长度 的信号L ，我们现在将其视为（将这N个元素值I mN去组成一个向量（Nx1）形式，该向量属于一 空间）。同理对于一个图像数据，我们将这个图像向量化成一个高维的向量来对待。对于空间I二一 中的任何一个向量（在这里想象成一个信号）都可以用二 空间 中的一组正交基表示出来。得到的是就是信号在这个空间中，该组基向量的对应坐标。 其中该组基向量为：为了简化分析，我们假设这组基为标准正交基。这组基组成的基矩阵为:巫：=如妙JMn那么我们要分析的信号X在该空间基下的坐标表示为：其中，Nx1的矩阵S为我们的原始信号在该基向量下的坐标(每个分量是我们要组成X 的所需的对应基向量的权重)。其中，对坐标系数的求解表达式子如下：齐=心fx不难看出(当已知基向量时)，其实S和X描述的是同一个信号(等价)。其中X位于信 号的时域中，S位于。接下来，我们将关注具有稀疏特性的那一类信号。也就是该信号X只需要k个基向量(注 意kN，也就是远小于N)进行稀疏表示(sparse representation)。也就是在表达式中，只有S中只有K个非零,剩下N-K个系数均为0。性质Sparsity来源于这样一个事实：大多数自然界中的信号和人工信号都是可以被压缩的，而且注意到在式子中，存在一组基，信号用这组基表示，只有少量的系数(坐标)值较大，其他系数都很小。所以， 我们用K-sparse representations能够很好的去近似这类可压缩的信号(Compressible signals )。这同时也是变换压缩编码(transform coding)背后隐含原理所在， 举个例子，自然图像(natural images)经过DCT变换后再压缩，称为J PEG压缩 编码方式，或者经过小波变换进行压缩，又称为J PEG-2000的格式压缩。音频信 号(Audio signals ) 中以及许多的通信信号(communication signals ) .采用局部傅里叶基(a localized Fourier basis)进行压缩。变换编码技术(Transform coding)在数据获取系统如数字照相机发挥着核心的 作用。因为在数据采集系统中，我们得到的数据样本数目非常大，但是得到信号 是可进一步压缩的信号。在变换编码时，我们采得N个样本的信号X，然后我们计算得到信号X在N个完全 基的坐标向量S：接下来，我们从向量S中选择出K个最大的数值，丢掉剩下N-K个小的系数。 最后对着K个系数进行编码,并且记录下这K个系数在向量S中的位置(便于重建) (在工程实践中，我们是对系数数值及其位置信息转换成二进制数)。然而不行的是，上述这种先采样，再压缩的模式(sample-then-compress) 本身隐藏着缺陷如下：1) 我们采集的数据N很大，但是最小我们的系数的个数K可能很小2) 编码器必须要计算出所有N个坐标系数(-J的大小，然后保留下K个最大的系数，丢弃掉剩下所有的系数。3）我们的编码器具有对这K个系数位置信息进行编码的开销 接下来我们将会学到一种新的更一般的数据获取方法（也就是压缩感知） 来替代上面讲到的先采样，再压缩的模式（sample-then-compress）。这种新的数 据采集方法不需要经过采集N个样本的中间阶段，而是将我们将要采集的信号直 接进行一种压缩表示出来。下面介绍一下该方法的实现原理如下：现在考虑一个更一般的线性测量过程（ more general linear measurement process），该测量过程同过计算我们要采集的信号X在一组（M个基向量）正交上的坐标实现（注意MvN ），其中对应坐标的计算公式为：的=g锦,然后将我们得到的M个坐标力组成一个M维的列向量y。并且将我们的再按顺序一行一行的排下去得到一个MxN的矩阵帀，这样我们的式子变为:然后将 1?二代入到上述式子中（注意是正交矩阵），得到:其中,是一个MxN的矩阵。用图形形象表示上述公式的具体情况如下：Figure 1: (a) Compressive sensing measurement process with (random Gaussian) measurement matrix and discrete cosine transform (DCT) matrix 亚.The coefficient vector s is sparse with K = 4. (b) Measurement process in terms of the matrix product 0 = W with the four columns corresponding to nonzero si highlighted. The measurement vector y is a linear combination of these four columns.根据上图a不难看出，该测量信号X的过程是非自适应的(non-adaptive), 也就是我们的测量矩阵小不会根据所要分析的信号的具体情况而做出具体的调 整。或者说，一旦选定相应的一组基向量，那么自始至终都不会改变。接下来，我们的目标就是设计一个测量矩阵，并且还要为我们的K稀 疏(K-sparse )和可压缩的(compressible)的信号X设计一个重建的算法(a reconstruction algorithm)。在这里所谓的K稀疏(K-sparse )和可压缩的 (compressible)的信号X,就是该类信号仅仅通过M K (或者稍微大于K个坐 标即可)的测量，就可以重建信号X。我们的重建算法是基于压缩感知的理论。 下面给出解决重建问题的方案。Solution：解决方案只需要两步即可。第一步，设计一个稳 定的测量矩阵(a stable measurement matrix )，该测量矩阵能 够保证在我们进行降维的时候(也就是利用线性变换矩 阵山将输入的信号工 二 降维到V -)，(尽管x 的维度下降，但是我们讲到我们的信号X是K稀疏(K-sparse ) 和可压缩的(compressible)的信号X),信号x中的突出的信息(the salient informatio n) 却保存下来。第二步，设计一个重建的算法(a reconstruction algorithm )，使得我们能 够从我们的测量信号y中重建出(高维度的)原始稀疏信号X。接下来，我们一步一步的介绍上述的解决方案。首先介绍稳定的测量矩阵小：这也是我们的数据采集系统要做的任务。 我们希望通过M次的测量（即获得了 M维的向量y）,然后通过能够稳定的去重 建原始的信号x（维度是N）（或者等价的，从稀疏系数向量s （对应的是原始信 号在基吐上的坐标向量）去重建）。很明显，如果在测量的过程中，如果我们采集的数据没有完全的得到X的 信息时，这时候利用测量的y去重建原始信号是不可能的。因为式子 r =印工=印亚-=卜丄是一个线性方程组，未知数的个数N是大于方程 个数M的，显然方程组有无数组解，何以重建我们的原始信号？！。在线代，此 类问题称为 ill-posed。显然，如果一个问题有无数组解时，那么说明我们的约束条件还不够，或 者给的信息还不够。我们可以通过添加约束条件使得该问题变成well-posed。一 个很明显的办法是增加方程的个数（如果这样，我们就没必要压缩感知了，我们 就又回到起点了）。还有一个就是对我们的信号X进行约束。也就是压缩感知的 核心，这就是假设我们的信号是K稀疏（K-sparse ）和可压缩的（compressible） 的信号，（为了能唯一重建我们的原始信号还需要一些条件，下面的充要条件）。 Ksparse 拯救了我们！在上述例子中，我们的测量的向量y只是矩阵（共有N列，M行）K （KN）个列的线性组合（对应于片工0的那些列）。所以，如果我们提前知道 了向量s的K个元素非零，我们就可以组成一个M x K （M个方程，K个未知量的 线性方程组，其中M稍大于K），这样问题就变得可解了。我们就可以运用现代 知识解出这K个非零值。保证线性方程组M x K有唯一解（well-conditioned ）的 充要条件是：对于任何一个具有和s的各个（共有K个）非零元素完全相同的N 维向量V，我们有：l-el + el|v|2 其中从表面上看，矩阵必须能够保持住这些Ksparse向量的 长度（模）。当然，我们在实践中并不知道向量s的这K个非零值所在的位置。然而有 趣的是，（当我们的信号是K稀疏（K-sparse ）和可压缩的（compressible），这 是大前提），我们对卜、要求其满足对于任意的Ksparse向量，都满 足上述的条件时，卜 就是a stable inverse，所求的原始信号就存在唯一解，完成重建。上述充分条件（不知道向量s的这K个非零值所在的位置）就是所谓的约 束等距性（restricted isometry property （RIP）。(另一保证 有stable inverse的办法就是保证我们的测量小与我们的稀 疏基矩阵（the sparsifying basis巫 ）是不连贯的。所谓的不连贯就是：向量组 也无法稀疏的去描述向量组