MATLAB稀疏重建OMP算法的并行优化(3)
1.2.1 匹配追踪类算法
匹配追踪类算法属于贪婪算法，每次找出单次迭代最优，最后可能得不到全局最优值，但是这类算法运算复杂度比较低，运行速度快，当精度要求不高的情况下实用性很好。1993年由S.G.Mallat提出的稀疏分解MP[6]算法是最早的用于压缩感知的匹配追踪算法。这个算法在每一次迭代中从字典矩阵里选择与信号最匹配的列对信号做稀疏接近，同时得到信号残差，接着继续选择与残差最匹配的列，反复迭代，直至残差为零，最后得到的逼近信号就是所求的重构信号。这个算法的不足是，信号在已选定原子即观测矩阵的列向量集合上投影并不一定是正交的，所以每次迭代的结果也不一定是最优的，所以需要较多的信号观测数目以及增加迭代次数。因此，文献[7]提出了正交匹配追踪（Orthogonal Matching Pursuit，OMP）算法。OMP算法和MP算法相差不大，不同的是OMP算法在每次迭代时都会对已选原子进行Schimidt正交化，这样可以得到当前迭代的最优值，以此减少测量数目和迭代次数。在此之后还有多候选集OMP（Multi-candidate OMP,MOMP）算法，树形匹配追踪（Tree Matching Pursuit,TMP）算法，正规化正交匹配追踪（Regularized Orthogonal Matching Pursuit,ROMP）算法，这些匹配追踪算法进一步提高了信号的重构精度，准确程度以及算法的运算速度。
1.2.2 最小化 范数算法
这种算法主要可以通过线性规划（Linear Program,LP）[8]求解，常用的求解方法是基追踪（Basis Pursuit,BP）方法。该方法精度高，计算复杂度比较高，需要的测量次数比较少。
1.2.3 迭代阙值算法
迭代阙值算法（Iterative Thresholding Algorithms）[9]主要针对前两种算法没有直接针对的 范数的求解。如果设置的初值合适，这个算法就能找到全局最优解，所以，这个迭代阙值算法可以和匹配追踪类算法相结合，相比于单独使用这些匹配追踪算法可以得到更好的效果。
1.2.4 梯度类算法
上面提到的三种算法比较适用于一文信号，当应用于二文信号时，需要把二文信号排列为一文信号，然后才能重构，算法运行速度比较慢，不太适合实际应用。因此相关学者经研究从离散梯度的角度提出了最小全变分法（Total Variation,TV）[10]，更适用于二文图像重建，因为很多自然二文图像的离散梯度都是稀疏的。之后又提出了梯度投影法（Gradient projection for Sparse Reconstruction,GPSR）和梯度追踪（Gradient Pursuit，GP）算法，用于求解压缩感知问题。有效提高了信号重建精度和运算速度。
以上仅是对几种重构算法的简单介绍，关于这些算法的详细叙述请参照[11]。本文主要研究正交匹配追踪（Orthogonal Matching Pursuit，OMP）算法的并行优化，在重构结果完全一致的情况下，提高算法运算速度。
1.3 研究工具介绍
1.3.1 SPAMS稀疏建模工具箱
SPAMS全称为SPArse Modeling Software,即稀疏建模软件，可以解决各种稀疏估计问题，并且是一个开源的优化工具箱，在其主页上可以找到关于这个工具箱的介绍，参考文献，以及一些提问和一些出现过的问题，在这个主页上可以下载到适用于MATLAB等软件的SPAMS工具箱。在下载的压缩包中的doc_spams.pdf文件对SPAMS工具箱各个函数接口的使用方法作了详细的的说明。
SPAMS工具箱可以实现多种用于解决机器学习的算法和稀疏重建的信号处理算法。主要分为三个模块，分别是字典学习和矩阵分解模块，应用快速下降算法、OMP算法，SOMP算法解决稀疏分解问题和结构化稀疏重建问题模块和近端模块。由于SPAMS工具箱中给出的代码是用C++编写的，所以在使用之前需要进行编译，也因此，SPAMS工具箱中的代码具有运行速度快，可移植性高的特点。