搜索
压缩感知理论包括三个关键技术：信号的稀疏表示、测量矩阵的设计与重构算法的研究。1信号的稀疏表示将N维信号在一组正交基{}(其中)是进行展开，得到：∑(1-1)其中。写成矩阵的形式可以得到：(1-2)其中[，，，]为正交基字典矩阵，[，，，]信号被称为项稀疏，表示其等价表示，向量中，只有项元素非零，其它元素全部为零。在我们研究的压缩感知中，主要考虑这种情况。这时，信号称为可压缩的。通过采用测量矩阵(行列，且)与式（1-2）中信号向量相乘，可以得到个测量结果，可写为：(1-3)式(1-3)中的列向量是信号的压缩线性测量结果(观测向量)。令公式（1-3）中，得到无噪声情况下的压缩感知的模型为：(1-4)显然，式（1-4）中A是维观测矩阵。而含有噪声的压缩感知模型为：(1-5)式(1-5)中为噪声项。恢复出了后，通过即可恢复出。接下来我们要做的是找到一个合适的观测矩阵，使得降维后的观测向量依然可以保存信号中的信息。然后由于式(1-5)是个欠定方程组，我们要寻找合适的重构算法来恢复。2观测矩阵的设计2.1受限等距性质信号能够重构的必要条件是测量矩阵满足受限等距性质RIP（Restrictedisometryproperty）。为了更好的描述看受限等跟性质的定义。定义2.1受限等距性质(RestrictedIsometryProperty，RIP)[7]：令观测矩阵的列范数归一化，稀疏度为自然数；任意向量，它最多只有项的非零元素，对于常数，满足下式：‖‖‖‖‖‖(2-1)那么，我们称，即称服从参数为的项稀疏，矩阵保存了项稀疏信号的信息。对于RIP特性的一个等价描述是：所有从中挑选出的列组成子集合形成的矩阵是近似列正交的。即保证中的列向量相互之间相关性尽量小。2.2几种具有良好受限等距性质的观测矩阵一许多随机矩阵都以很高的概率符合RIP特性。高斯矩阵，伯努利矩阵和部分的随机傅里叶矩阵，或者说，几乎所有的满足独立同分布(IndependentIdenticallyDistribution，IID)的矩阵都以很高的概率符合RIP条件。实际应用中，随机性在理论上有了充分的保证，但是它却很难实用，并且还要求额外的存储空间来保存测量矩阵。另外，在一些应用中，并不允许随机矩阵。例如，在无线通信应用领域，信号的传输过程可看做是传输信号与信道的卷积，其中卷积是一种线性循环操作。这种卷积过程，形成了一种结构性的，随机性削弱的矩阵。尽管如此，随机的托普利兹和循环矩阵却能容易地在不同应用中实现，而且，经过特意设计的循环矩阵同样能达到理想的压缩感知性能。3信号的重构算法在压缩感知理论中，因为观测向量的观测数量远小于信号的长度，所以从方程组的角度来看式（1-4）是一个欠定方程组。从数学角度来说，欠定方程组是无解的，但是，因为信号是稀疏的，使得方程组有解。观测矩阵的RIP性质为从个测量值中恢复稀疏信号提供了理论保证。定义3.1向量{}的范数为：‖‖(∑)当定义3.1中的时得到0-范数，它表示向量中非零元的个数。于是在信号是稀疏的和测量矩阵满足受限等距性质的前提下，求解欠定方程组的问题转为最小0-范数问题：‖‖使得不难发现上述解是一个NP（Non-deterministicPolynomialhard）问题。针对这个问题有两种解决方法。第一种是凸松弛方法，将0-范数问题变换为1-范数最小化问题，这种解法也称为基追踪，其依赖于线性规划方法；另一种解法则是使用贪婪算法，譬如变化的匹配追踪算法，正交匹配追踪算法等等，通过迭代寻找，得到最优解。此外，还有一些其它的算法基于不同的视角发展而来，像迭代阈值算法，迭代支撑检测算法等。对于不同种类的途径，可以得到不同种类的重构算法。基于观测矩阵的不同设计，对于具有相同的信号长度和相同的稀疏度，不同的算法要不同数量(这个数量等于)的观测结果，并且它们提供不同的准确恢复概率。下面我们以式（1-4）或式（1-5）进行分析，详述压缩感知常用的重构算法。3.1凸优化算法压缩感知重构算法里面基于凸优化算法的主要有两种。第一种是Dantzig选择器(DantzigSelector，DS)，它依然是一种基于1-范数正则化问题的解。当存在噪声的情况时，DS方法性能相当好，并且它的计算复杂度是可追踪的，因为它可以投射为一个线性规划的问题。另外它的性能界也好分析，对于稀疏信号以及近似稀疏信号他们重构所引起的误差范围很方便判断。另外一种是基追踪(BasisPursuit，BP)算法即基于1-范数最小化求解为：‖‖使得（3-1）而对于处理存在噪声的情况，即演化为下述问题：‖‖使得‖‖（3-2）其中阈值由观测噪声决定。对于式(3-1)以及(3-2)，不同的凸优化技术可以有效地用来解决上面的问题，如同伦法、内点法、梯度投影法；另外我们可以借助于“CVX”工具箱在MATLAB上仿真求解。3.2贪婪迭代算法为另一类运算量小更易于实现稀疏信号重建算法是贪婪迭代的算法。贪婪算法是指在求解问题时，一步步进行，在每一步不从整体上加以考虑，而从当前角度来看，做出最好的选择，或称其为局部意义上的最佳解，经过多次迭代以后得到问题的最优解。下面我们将分析常见算法。为了更好的描述这些算法，我们先对一些符号和等式进行概念上的说明。对压缩感知的模型：来说，是维的列向量，是维的矩阵，是的列向量。并且，中只有个为非零的元素，其它元素为零。我们要做的就是把中的非零的元素的位置和值找出来。为了表述方便，我们用记，，[，，，]，稀疏度为K。3.2.1匹配追踪算法（MP算法）匹配追踪(MatchingPursuit，MP)是一种贪婪迭代算法。MP算法的基本思想是在每一次代的过程中,从过完备原子库(测量矩阵)中选择与信号最匹配的原子即测量矩阵中的列向量来进行稀疏逼近，并求出残余量，然后继续选取与残余量最匹配的原子。经过数次迭代后,原稀疏信号便可以近似地使用这些原子线性表示。MP算法的流程如下：（1）初始化：初始测量向量的逼近，残余量，迭代次数，索引集合，稀疏度，{}，初始原子集合（2）挑选索引，计算内积的绝对值，找出相关性最高的原子在测量矩阵中对应的索引：（3）更新索引集合{}，挑选原子集合,（4）计算新的测量向量的逼近向量和新的残余量：（5）判断：迭代结束；否则，重复2-4步骤，进入下一次迭代。进行完上述MP算法的流程后，对原来的欠定方程组来说，维列向量中，在索引集合位置处的值为，其它位置的值为0。这样我们就把的近似解求了出来。MP算法的复杂度低，它保证了每次的残余量与这次所选的原子是正交的，但残余量与前面所选的原子的关系就不一是正交的了。这样的话，我们得到的解可能就不是最优解了。所以就有了下面的基于MP算法的改进算法。3.2.2正交匹配追踪算法（OMP算法）OMP算法SignalRecoveryFromRandomMeasurementsviaOrthogonalMatchingPrusuit.pdfOMP算法和MP算法的主要步骤和思想基本相同，只是在计算估计的的系数和更新残余量时有所区别，它在每次挑选的原子集合中，进行了正交化处理过程，也使得在精度相同的情况下，OMP算法的收敛速度更快。OMP算法流程如下所示：（1）初始化，索引集合，迭代次数，残差量，初始原子集合。（2）挑选索引，计算内积的绝对值，找出相关性最高的原子在字典中对应的索引，即满足：（3）更新索引集合{}，挑选的原子集合,。（4）计算估计的稀疏系数，其中；更新残余量。（5）如果，迭代结束，否则，重复2-4步骤，进入下一次迭代。估计的稀疏解是一个的向量，对应于索引处的元素值等于维向量的个值（与索引位置一一对应），而其它元素皆为“0”。OMP算法相比MP算法而言，保证了每次选择最优的原子，降低了迭代次数。OMP算法的迭代速度快和易于实现，它的复杂度为O（MNK）但是OMP每次进行选择的过程中，只挑选了内积绝对值最大即相关度最高的原子来更新挑选的原子集合，我们可以进一步改进，即一次选取多个原子加入集合，这就是下面要描述的算法。2.4.2.5广义OMP算法广义OMP分析-GeneralizedOrthogonalMatchingPursuit.pdf确切来说广义OMP算法是对OMP算法的一种推广，我们知道，在OMP算法中，每次迭代只会增加一个原子，而在广义OMP算法里，每次增加的原子数目为，为整数，我们记这种算法为gOMP-n，算法流程如下：（1）初始化，索引集合，迭代次数，残差量，初始原子集合。预先给定的使迭代停止的阈值。（2）挑选索引，计算，找出中最大的个元素所对应的位置坐标集合（注意这里中有个元素）。（3）更新索引集合{}，挑选的原子集合,表示在选出集合‖‖个维列向量，的值取集合中的元素。（4）计算估计的稀疏系数，其中；更新残余量。（5）如果{⁄}或者‖‖，迭代结束，否则，重复2-4步骤，进入下一次迭代。广义OMP算法比OMP算法收敛更快，它实际上包含了OMP算法（当时）。都是递归的算法MP算法：投影余量与当前原子正交OMP算法：投影余量与所有原子正交Ak,rK=AkTy-AkT=0（此处的0是个向量）上式即表示余量rk和当前所有原子Ak都正交举例说明：稀疏度K=2M=4N=8Y=AX0.20270.29380.19691.15480.93050.55120.35350.13210.11680.15800.00100.80310.12820.17800.15250.40900.46670.1.10080.97420.12570.34390.38280.27010.12750.72260.29890.6043YAX1234567806950.38280.00530.11290.73690.60431.08060.26350.5201xxxxxxxx我们要通过以上模型求出X，X是个稀疏向量，只有两个非零值假设A=（a1a2a3a4a5a6a7a8）步骤1.初始化余量R=Y迭代次数k=1步骤2.计算内积0.03020.71370.20560.49700.27900.04740.70541.0987TRA上述向量中的8个值表示余量与各列（a1a2a3a4a5a6a7a8）的内积，即余量与各列的相关程度步骤3.取内积的绝对值最大的列，加入索引集。并且根据索引集更新原子集。在步骤2的内积的绝对值最大是1.0987，是第1列，把1加入索引集，原子集更新为｛a1｝步骤4用最小二乘方法估计系数和更新余量估计的模型是由原子集的所有原子和一开始的观测向量Y建立起来的Y=a1*x1得出估计结果x1=1.0418更新余量110.10860.1570*0.08590.4026RYax步骤5判断迭代停止条件如果满足迭代次数小于或等于稀疏度K或者余量小于阈值，那么迭代结束，否则重复步骤2到4且k=k+1此时k=12所以继续重复步骤2到4k更新为2步骤6（步骤2）计算内积0.00000.13290.04470.21630.36020.15540.14800.5375TRA步骤7（步骤3）取步骤6中内积的绝对值最大的列是第6列把6加入索引集，此时索引集=｛1，6｝对应的原子集=｛a1,a6｝步骤8（步骤4）估计系数和更新余量估计模型为1166xYaax用最小二乘得到估计结果11.132060.3825xx更新余量11660.00490.0004**0.00000.0011RYaxax步骤9此时k=2达到迭代终止条件算法结束得到最终的X的估计结果为1.132000000.382500X