MATLAB稀疏重建OMP算法的并行优化

摘要复原算法是压缩感知（CS）中的关键内容。目前，用于压缩感知的一个流行的复原算法是正交匹配追踪算法（OMP），该算法具有低复杂度和良好的恢复质量的优点。考虑到OMP算法涉及大量的矩阵和向量操作，这使这个算法非常适合并行优化处理。也正因为这些大量的矩阵和向量操作使的OMP算法的运行速度受到影响，所以需要运用一些方法对OMP算法进行并行优化，加快算法运行速度。30640
本文主要研究通过改进正交匹配追踪算法实现算法的并行优化，并通过对比实验得到改进算法与原始算法的加速比。本文的主要工作如下：
（1）研究OMP算法各个部分的复杂度并且分析影响算法计算速度的瓶颈；
（2）改进OMP算法的MATLAB代码，实现算法的并行优化；
（3）运用MATLAB中parfor工具实现并行优化；
（4）运用SPAMS工具箱测试改进后的OMP算法的正确性和加速效果。
关键词压缩感知正交匹配追踪并行优化加速比
毕业设计说明书外文摘要
Title     Parallel Optimization of Orthogonal Matching Pursuit for Compressed Sensing
Abstract
Recovery algorithms play a key role in Compressed Sensing (CS). Recently, a widely used recovery algorithm for Compressed Sensing is the orthogonal matching pursuit (OMP) with low complexity and good quality of recovery. Because the OMP algorithm involves a lot of matrix/vector calculation, it is very suitable for parallel optimization .Because of a large number of matrix and vector operations,the speed of the OMP algorithm is affected. It is necessary to use some method of parallel optimization of OMP algorithm to accelerate its speed.
This paper studies on the parallel optimization of the orthogonal matching pursuit algorithm by improving the orthogonal matching pursuit algorithm and get the speedups of the improved algorithms comparing with the original algorithm by some experiment. The main work is as follows:
(1)Study on the complexity of each part of the OMP algorithm and analyze the bottleneck impacting the speed of calculation;
(2)Improve the MATLAB code of OMP algorithm to achieve parallel optimization algorithm in the part of code;
(3)Use parfor tools in MATLAB for parallel optimization;Use spams to test the accuracy and speedups of the improved OMP algorithm.
Keywords Compressed Sensing； Orthogonal Matching Pursuit ； Parallel Optimization； speedups
目   次
1 引言1
1.1 压缩感知概述1
1.2 信号重构算法概述 2
1.2.1 匹配追踪类算法 2
1.2.2 最小化L2范数算法2
1.2.3 迭代阙值算法2
1.2.4 梯度类算法2
1.3 研究工具介绍3
1.3.1 SPAMS稀疏建模工具箱3
1.3.2 MATLAB并行工具parfor指令4
1.4 课题研究的主要内容 4
1.5 章节安排5
2   稀疏重建OMP算法的介绍与分析6
2.1 稀疏重建OMP算法的说明6
2.2 稀疏重建OMP算法的分析7
2.2.1 OMP算法复杂度分析7
2.2.2 OMP算法加速瓶颈分析8
2.3 本章小结8
3 OMP算法的并行优化改进9
3.1 OMP算法的代码改进9
3.2 OMP算法的MATLAB并行计算优化10
3.3 本章小结11
4   改进OMP算法的测试和对比试验12
4.1 改进OMP算法的测试12
4.2 三种OMP算法运行时间对比实验13 MATLAB稀疏重建OMP算法的并行优化:http://www.youerw.com/jisuanji/lunwen_26464.html