压缩感知重构之匹配追踪算法

算法的重构是压缩感知中重要的一步，是压缩感知的关键之处。因为重构算法关系着信号能否精确重建，国内外的研究学者致力于压缩感知的信号重建，并且取得了很大的进展，提出了很多的重构算法，每种算法都各有自己的优缺点，使用者可以根据自己的情况，选择适合自己的重构算法，大大增加了使用的灵活性，也为我们以后的研究提供了很大的方便。

压缩感知的重构算法主要分为三大类：

1.组合算法   2.贪婪算法  3.凸松弛算法

三种算法对比分析如下：

算法类别	定义	优缺点	具体算法
贪婪算法	贪婪算法首先选取合适的原子，再逐步进行递增，进而逼近信号矢量，利用这种过程进行	计算量和精度的要求居中，也是三种重构算法中应用最大的一种	(1)匹配追踪算法 (2)正交匹配追踪算法 (3)分段正交匹配追踪算法 (4)正则化正交匹配追踪算法 (5)稀疏自适应匹配追踪算法
组合算法	先是对信号进行结构采样，然后再通过对采样的数据进行分组测试，最后完成信号的重构	需要观测的样本数目比较多但运算的效率最高	(1) 傅里叶采样 (2) 链式追踪算法 (3)  HHS追踪算法
凸松弛算法	法，它将非凸问题转化为凸问题进行求解，即l0范数转化成l1范数并采用线性规划来求解	计算量大但是需要观测的数量少重构的时候精度高	(1)基追踪算法 (2)最小全变差算法 (3)内点法 (4)梯度投影算法 (5)凸集交替投影算法

本篇主要分析匹配追踪算法（Matching Pursuit  MP）

匹配追踪算法是Mallat和ZHANG在小波分析的基础上提出的，是贪婪迭代算法中的比较基本的算法，有其显著的特点，是学习研究贪婪算法的基础。

1、MP算法的原理

 其中测量矩阵又称为过完备字典，每一列被称为一个原子，则测量矩阵中有n个原子，而y的长度为m，原子的个数远远大于信号的长度，即m<<n，因此测量矩阵又称为过完备字典。信号y在测量矩阵上进行分解，单位向量长度为1，要对过完备字典的原子进行归一化处理。

MP算法的基本思想：

从观测矩阵（过完备字典）中选择一个与信号y相关性最大（最匹配）的原子，也就是观测矩阵中的一列，构建信号的稀疏逼近，求出信号的残差，重复上面的操作，继续选择与信号残差最匹配的一个原子，如此反复迭代直到达到迭代次数，最后信号y就可以表示为这些原子的线性组合。

2、MP算法的理论框图

根据MP算法的原理，得出MP算法的理论图，这样更容易理解。

 3、MP算法的算法流程

根据MP算法的理论框图，现在写出MP算法的算法流程，这样让我们对MP算法有一个更加清晰的理解。

  4、MP算法的信号重构

分别通过对一维离散信号，二维Lena为例，进行MP算法的信号重构。

（1）一维离散信号的MP算法仿真

  本次仿真使用matlab随机生成的一维离散信号，稀疏度k=23,信号长度N=256，观测向量的长度M=80，那么采样率M/N=0.3，其中的观测矩阵是高斯随机矩阵。采用MP算法对一维信号进行重构，重构图：

通过上面的重构可以得出，MP算法对一维信号有很好的重构效果。

（2）二维lena图像的MP算法重构

        我们上面的研究知道MP算法对一维信号有很好的重构作用，但是算法不只是要在一维信号中有好的重构功能，还要能很好的重构二维信号才可以，这样应用的范围才会更大。我们知道压缩感知重构的是可压缩的稀疏信号，二维信号是不稀疏的，这就要在进行算法重构的时候进行一些处理，我们可以先采用离散余弦变换（dct）使数据稀疏，算法重构结束之后再进行离散反余弦变换（idct），这样就转化为了我们所需要的。本次在matlab中的仿真，我们采用的是256X256的Lena的二维图像，M=180，N=256，稀疏度k=40，M/N=0.7，观测矩阵是高斯随机矩阵，采用MP算法对二维图像进行重构，重构效果如图：

 采样率为0.7的时候，MP算法也能对二维图像进行精确重构。