压缩感知总结

1、压缩感知理论包括三个关键技术：信号的稀疏表示、测量矩阵的设计与重构算法的研究。1 信号的稀疏表示将N维信号xRN×1在一组正交基ii=1N(其中iRN×1)是进行展开，得到：x=i=1Nii (1-1)其中i=<x,i>=iTx。写成矩阵的形式可以得到：x= (1-2)其中=i，2，NRN×N为正交基字典矩阵，=i，2，NT信号x被称为K项稀疏，表示其等价表示，向量中，只有K项元素非零，其它元素全部为零。在我们研究的压缩感知中，主要考虑KN这种情况。这时，信号x称为可压缩的。通过采用测量矩阵M×N(M行N列，且M<N)与式（1-2）中信

2、号向量x相乘，可以得到M个测量结果，可写为： y= (1-3)式(1-3)中M×1的列向量y是信号x的压缩线性测量结果(观测向量)。令公式（1-3）中A=，得到无噪声情况下的压缩感知的模型为：y=A (1-4)显然，式（1-4）中A是M×N维观测矩阵。而含有噪声的压缩感知模型为：y=A+z (1-5)式(1-5)中z为噪声项。恢复出了后，通过x=即可恢复出x。接下来我们要做的是找到一个合适的观测矩阵A，使得降维后的观测向量y依然可以保存信号中的信息。然后由于式(1-5)是个欠定方程组，我们要寻找合适的重构算法来恢复。2 观测矩阵的设计2.1 受限等距性质信号能够重构的必要条

3、件是测量矩阵A满足受限等距性质RIP（Restricted isometry property）。为了更好的描述看受限等跟性质的定义。定义2.1受限等距性质(RestrictedIsometry Property，RIP)7：令观测矩阵A的列范数归一化，稀疏度K为自然数；任意向量v，它最多只有K项的非零元素，对于常数K(0,1)，满足下式：1-Kv22Av221+Kv22(2-1)那么，我们称ARIP(K,K)，即称A服从参数为K的K项稀疏，矩阵A保存了K项稀疏信号的信息。对于RIP特性的一个等价描述是：所有从A中挑选出的K列组成子集合形成的矩阵是近似列正交的。即保证A中的列向量相互之间相关性

4、尽量小。2.2 几种具有良好受限等距性质的观测矩阵一许多随机矩阵都以很高的概率符合RIP特性。高斯矩阵，伯努利矩阵和部分的随机傅里叶矩阵，或者说，几乎所有的满足独立同分布(Independent Identically Distribution，IID)的矩阵都以很高的概率符合RIP条件。实际应用中，随机性在理论上有了充分的保证，但是它却很难实用，并且还要求额外的存储空间来保存测量矩阵。另外，在一些应用中，并不允许随机矩阵。例如，在无线通信应用领域，信号的传输过程可看做是传输信号与信道的卷积，其中卷积是一种线性循环操作。这种卷积过程，形成了一种结构性的，随机性削弱的矩阵。尽管如此，随机的托普利

5、兹和循环矩阵却能容易地在不同应用中实现，而且，经过特意设计的循环矩阵同样能达到理想的压缩感知性能。3 信号的重构算法在压缩感知理论中，因为观测向量y的观测数量M远小于信号x的长度N，所以从方程组的角度来看式（1-4）是一个欠定方程组。从数学角度来说，欠定方程组是无解的，但是，因为信号x是稀疏的，使得方程组有解。观测矩阵的RIP性质为从M个测量值中恢复稀疏信号x提供了理论保证。定义 3.1 向量X=x1,xn的p-范数为：Xp=i=1n|x1|p1p当定义3.1中的p=0时得到0-范数，它表示向量X中非零元的个数。于是在信号x是稀疏的和测量矩阵A满足受限等距性质的前提下，求解欠定方程组y=A的问

6、题转为最小0-范数问题： min'0使得y=A' 不难发现上述解是一个NP（Non-deterministic Polynomial hard）问题。针对这个问题有两种解决方法。第一种是凸松弛方法，将0-范数问题变换为1-范数最小化问题，这种解法也称为基追踪，其依赖于线性规划方法；另一种解法则是使用贪婪算法，譬如变化的匹配追踪算法，正交匹配追踪算法等等，通过迭代寻找，得到最优解。此外，还有一些其它的算法基于不同的视角发展而来，像迭代阈值算法，迭代支撑检测算法等。对于不同种类的途径，可以得到不同种类的重构算法。基于观测矩阵A的不同设计，对于具有相同的信号长度N和相同的稀疏度K，不

7、同的算法要不同数量(这个数量等于M)的观测结果，并且它们提供不同的准确恢复概率。下面我们以式（1-4）或式（1-5）进行分析，详述压缩感知常用的重构算法。3.1 凸优化算法压缩感知重构算法里面基于凸优化算法的主要有两种。第一种是Dantzig选择器(Dantzig Selector，DS)，它依然是一种基于1-范数正则化问题的解。当存在噪声的情况时，DS方法性能相当好，并且它的计算复杂度是可追踪的，因为它可以投射为一个线性规划的问题。另外它的性能界也好分析，对于稀疏信号以及近似稀疏信号他们重构所引起的误差范围很方便判断。另外一种是基追踪(Basis Pursuit，BP)算法即基于1-范数最小

8、化求解为：min'1使得y=A'（3-1）而对于处理存在噪声的情况，即演化为下述问题：min'1使得y-A'2（3-2） 其中阈值由观测噪声z决定。对于式(3-1)以及(3-2)，不同的凸优化技术可以有效地用来解决上面的问题，如同伦法、内点法、梯度投影法；另外我们可以借助于“CVX”工具箱在MATLAB上仿真求解。3.2贪婪迭代算法为另一类运算量小更易于实现稀疏信号重建算法是贪婪迭代的算法。贪婪算法是指在求解问题时，一步步进行，在每一步不从整体上加以考虑，而从当前角度来看，做出最好的选择，或称其为局部意义上的最佳解，经过多次迭代以后得到问题的最优解。下面我们将分

9、析常见算法。为了更好的描述这些算法，我们先对一些符号和等式进行概念上的说明。对压缩感知的模型：y=A来说，y是M×1维的列向量，A是M×N维的矩阵，是N×1的列向量。并且MN，中只有K个为非零的元素，其它元素为零。我们要做的就是把中的非零的元素的位置和值找出来。为了表述方便，我们用记A=(1,2,N)，iRM×1，i=1,2,N=1，2，NT，稀疏度为K。3.2.1匹配追踪算法（MP算法）匹配追踪(Matching Pursuit，MP)是一种贪婪迭代算法。MP算法的基本思想是在每一次代的过程中, 从过完备原子库( 测量矩阵) 中选择与信号最匹配的原子即

10、测量矩阵中的列向量来进行稀疏逼近，并求出残余量，然后继续选取与残余量最匹配的原子。经过数次迭代后, 原稀疏信号便可以近似地使用这些原子线性表示。MP算法的流程如下：（1）初始化：初始测量向量y的逼近B0=0，残余量r0=y，迭代次数k=1，索引集合=，稀疏度K，=1,2,N，初始原子集合A0=（2）挑选索引，计算内积的绝对值，找出相关性最高的原子在测量矩阵中对应的索引(k)：(k)=w=1,Nargmax|<rk-1,w>|（3）更新索引集合k=k-1 (k)，挑选原子集合Ak=Ak-1,(k)（4）计算新的测量向量y的逼近向量Bk和新的残余量rk：Bk=Bk-1+<rk-1

11、,(k)>(k)rk=y-Bk（5）判断：k>K迭代结束；否则k=k+1，重复2-4步骤，进入下一次迭代。进行完上述MP算法的流程后，对原来的欠定方程组y=A来说，N×1维列向量中，在索引集合位置处的值为<rk-1,(k)>，其它位置的值为0。这样我们就把的近似解求了出来。MP算法的复杂度低，它保证了每次的残余量rk与这次所选的原子k是正交的，但残余量rk与前面所选的原子的关系就不一是正交的了。这样的话，我们得到的解可能就不是最优解了。所以就有了下面的基于MP算法的改进算法。3.2.2正交匹配追踪算法（OMP算法） OMP算法和MP算法的主要步骤和思想基本相同

12、，只是在计算估计的的系数和更新残余量时有所区别，它在每次挑选的原子集合中，进行了正交化处理过程，也使得在精度相同的情况下，OMP算法的收敛速度更快。OMP算法流程如下所示：（1）初始化，索引集合=，迭代次数k=1，残差量r0=y，初始原子集合A0=。（2）挑选索引，计算内积的绝对值，找出相关性最高的原子在字典中对应的索引(k)，即满足：(k)=w=1,Nargmax|<rk-1,w>|（3）更新索引集合k=k-1 (k)，挑选的原子集合Ak=Ak-1,(k)。（4）计算估计的稀疏系数k=(Ak)y，其中(Ak)=(AkTAk)-1AkT；更新残余量rk=y-Akk。（5）如果k&g

13、t;K，迭代结束，否则k=k+1，重复2-4步骤，进入下一次迭代。估计的稀疏解是一个N×1的向量，对应于索引k处的元素值等于K×1维向量k的K个值（与索引位置一一对应），而其它元素皆为“0”。OMP算法相比MP算法而言，保证了每次选择最优的原子，降低了迭代次数。OMP算法的迭代速度快和易于实现，它的复杂度为O（MNK）但是OMP每次进行选择的过程中，只挑选了内积绝对值最大即相关度最高的原子来更新挑选的原子集合，我们可以进一步改进，即一次选取多个原子加入集合，这就是下面要描述的算法。2.4.2.5广义OMP算法确切来说广义OMP算法是对OMP算法的一种推广，我们知道，在OMP

14、算法中，每次迭代只会增加一个原子，而在广义OMP算法里，每次增加的原子数目为n，n为整数，我们记这种算法为gOMP-n，算法流程如下：（1）初始化，索引集合=，迭代次数k=1，残差量r0=y，初始原子集合A0=。预先给定的使迭代停止的阈值。（2）挑选索引，计算u=ATr0，找出u中最大的n个元素所对应的位置坐标集合k（注意这里k中有n个元素）。（3）更新索引集合k=k-1 (k)，挑选的原子集合Ak=Ak-1,A(k)A(k)表示在A=(1,2,N)选出集合k0个M×1维列向量i，i的值取集合A(k)中的元素。（4）计算估计的稀疏系数k=(Ak)y，其中(Ak)=(AkTAk)-1A

15、kT；更新残余量rk=y-Akk。（5）如果k>minK,Mn或者rk2，迭代结束，否则k=k+1，重复2-4步骤，进入下一次迭代。广义OMP算法比OMP算法收敛更快，它实际上包含了OMP算法（当N=1时）。都是递归的算法MP算法：投影 余量与当前原子正交OMP算法：投影 余量与所有原子正交 rk=y-Ak(AkTAk)-1AkTy <Ak,rK>=AkTy-AkT(AkTAk)-1AkTy=0（此处的0是个向量）上式即表示余量rk 和当前所有原子Ak都正交举例说明：稀疏度K=2 M=4 N=8 Y = A X我们要通过以上模型求出X，X是个稀疏向量，只有两个非零值假设A=（a1 a2 a3 a4 a5 a6 a7 a8）步骤1.初始化 余量R=Y 迭代次数k=1步骤2.计算内积 上述向量中的8个值表示余量与各列（a1 a2 a3 a4 a5 a6 a7 a8）的内积，即余量与各列的相关程度 步骤3. 取内积的绝对值最大的列，加入索引集。并且根据索引集更新原子集。 在步骤2的内积的绝对值最大是1.0987，是第1列，把1加入索引集，原子集更新为a1 步骤4 用最小二乘方法估计系数和更新余量 估计的模型是由原子集的所有原子和一开始的观测向量Y建立起来的Y=a1*x1 得出估计结果 x1=1.