（信号与信息处理专业论文）压缩感知中信号重建算法和确定性测量矩阵研究.pdf

research on signal reconstruction algorithm and deterministic measurement matrix in compressed sensing this is submitted to nanjing university of posts and telecommunications for the degree of master of engineering by liang-long yang supervisor: prof. sheng-mei zhao feb. 2013 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。 南京邮电大学学位论文使用授权声明 本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文 档；允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索； 可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质 论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院办理。涉密学位论 文在解密后适用本授权书。 研究生签名：_ 日期：_ 研究生签名： _ 导师签名： _ 日期： _ i 摘要摘要 压缩感知是集采样、压缩和编码于一身的、利用信号稀疏性进行信号压缩和采样的一种 新型理论。它通过求解凸优化问题，利用少量采样值实现稀疏信号的精确重建。其中，信号 重建算法和测量矩阵是压缩感知的两个关键部分。论文着重研究了压缩感知的信号重建算法 和确定性测量矩阵。主要工作如下： (1) 针对压缩感知理论中的信号重建算法，总结了贪婪算法中几种常见算法的几何模型 和算法步骤，包括匹配追踪算法(matching pursuit, mp)、正交匹配追踪算法(orthogonal matching pursuit, omp)、正则化正交匹配追踪算法(regularization orthogonal matching pursuit, romp)、分段式正交匹配追踪算法(stagewise orthogonal matching pursuit, stomp)、压缩采样 匹配追踪算法(compressive sampling matching pursuit, cosamp)、子空间追踪算法(subspace pursuit, sp)和最近出现的前向后向匹配追踪(forward-backward pursuit, fbp)算法。 然后采用我 们所熟悉的lina图对各类算法进行性能比较，结果表明在相同的压缩比和测量矩阵的条件下， sp、cosamp和fbp算法的信噪比和峰值信噪比都要比mp、omp、romp和stomp算法高2db 左右。最后对fbp算法进行改进并作出性能仿真分析，实验结果表明改进的fbp算法与原始算 法相比虽然信噪比只增加了0.3db，峰值信噪比也只增加了0.3db，但是在相同压缩比和不同 压缩比的条件下，信号重建时间都有一定程度的减少，当压缩比为“1”的条件下，重建时间 可减少10s。 (2) 论文对sl0算法中涉及到的最优值求解思想进行了研究，发现它的迭代方向为负梯度 方向，存在“锯齿效应” ，并且sl0算法及其改进算法(nsl0)中的连续函数“陡峭性”不大， 论文提出一种结合修正牛顿法和阻尼牛顿法的信号重建算法。数值计算结果表明改进的sl0 算法相对于sl0算法可在峰值信噪比和信噪比上提高2db，且相对误差也能改善1%左右。 (3) 利用传统信道编码中校验矩阵计算速度快，感知效率较高、需要的物理内存较少且 易于硬件实现的优点，并对校验矩阵进行相应的数学操作，论文提出一种基于信道编码的压 缩感知测量矩阵构造方法。数值计算结果证明，基于信道编码的测量矩阵的压缩感知算法性 能无论在视觉效果上还是在客观数据上都要优于高斯随机测量矩阵的压缩感知算法性能，且 优于或者近似于同类确定性测量矩阵，如贝努利测量矩阵、哈达玛测量矩阵和多项式测量矩 阵等。在相同的压缩比和重建算法的条件下，相比于上述确定性测量矩阵，信噪比和峰值信 噪比可有 3db 的提高，相对误差更小（约 1%左右)；但重构时间相对较长一些。 关键词关键词: 信号处理；压缩感知；重建算法；测量矩阵； ii abstract compressed sensing theory is a novel signal sampling and compression theory under the condition that the signal is sparse, which combines sampling、 compression and encoding together. it needs a small amount of sample values to reconstruct the original sparse signal in a high probability by solving a convex optimization problem. signal reconstruction algorithm and measurement matrix is the two key steps of compressed sensing, in this paper, properties of existing reconstruction algorithm and deterministic measurement matrix are firstly analyzed. based on that, the main contributions of this paper are summarized as follows. here, we summarize several common geometric model of the greedy algorithm in compressed sensing, including mp(matching pursuit), omp(orthogonal matching pursuit), romp(regularization orthogonal matching pursuit), stomp(stagewise orthogonal matching pursuit), cosamp (compressive sampling matching pursuit), sp(subspace pursuit)and fbp(forward-backward pursuit). under the condition of the same compression ratio and measurement matrix, it is shown that sp、 cosamp and fbp are higher 2db on snr and psnr than mp, omp, romp and stomp through the simulation using the lina figure. at last, we improve the fbp algorithm and compare the performance of the two algorithms, the result shows that the improved algorithm are higher 0.3db on snr and psnr, but under the condition of the same compression ratio and the different compression ratio the reconstruction time is lower than fbp. this paper has thoroughly research the smoothed l0 norm algorithm (sl0), which involves the thought in solving the optimal values. it has “notched effect” due to the negative iterative gradient direction. moreover, the property of continuous function in sl0 and its improved algorithm (nsl0) is not steep enough, which results in the estimations are not accurate and the convergence is slow. in this paper, combined with the damped newton method and the revised newton method we propose a novel reconstruction algorithm, which has great improvement in both psnr and snr, which are higher 2db. the relative error also improved about 1%. at last, we proposed a new measurement matrix construction method in compressed sensing, which is based on the channel coding, this method uses the advantages of the check matrix in the traditional coding, for example, computing fast、less physical memory and easy hardware implementation, through the corresponding processing, we can obtain the measurement matrix which is satisfy the requirements of compressed sensing. the experimental results show that the iii proposed method can get better reconstruction performances and it is superior to other random measurement matrix and superior or approximate to the deterministic measurement matrix both visually and objectively on the experimental data, the psnr and snr, which are higher 3db. the relative error also improved about 1%, but the reconstruction time is longer relatively. key words: signal processing; compressed sensing; reconstruction algorithm; measurement matrix iv 目录目录 第一章 绪论. 1 1.1 课题研究背景及意义. 1 1.2 本文主要工作和结构安排. 2 第二章 压缩感知理论框架. 3 2.1 压缩感知理论简介. 3 2.2 压缩感知数学模型. 3 2.3 压缩感知重构算法简介. 7 2.4 压缩感知测量矩阵简介. 9 2.5 本章小结.11 第三章 基于 cs 理论的图像重构算法. 12 3.1 贪婪算法. 12 3.1.1 匹配追踪算法(mp). 12 3.1.2 正交匹配追踪算法(omp). 14 3.1.3 正则化正交匹配追踪算法(romp). 15 3.1.4 分段式正交匹配追踪算法(stomp). 16 3.1.5 压缩感知匹配追踪算法(cosamp) . 17 3.1.6 子空间追踪算法(sp). 18 3.1.7 子前向后向匹配追踪算法(fbp)及其改进算法. 19 3.2 各种贪婪算法的实验结果和分析 . 21 3.3 本章小结. 24 第四章 基于 sl0 压缩感知信号重建的改进算法. 26 4.1 基于 sl0 改进算法的提出. 26 4.1.1 sl0 算法过程及理论基础. 26 4.1.2 基于 sl0 改进算法近似 l0 范数估计及具体实现. 28 4.1.3 改进算法步骤. 31 4.2 改进算法的实验结果和分析 . 32 4.2.1 基于 sl0 不同改进算法的实验结果. 32 4.2.2 三类不同算法的实验结果 . 33 4.2.3 三种不同算法的实验结果 . 34 4.3 本章小结. 37 第五章 基于信道编码压缩感知测量矩阵的构造方法. 38 5.1 基于压缩感知信道编码理论简介 . 38 5.2 基于信道编码的测量矩阵构造方法 . 42 5.2.1 构造方法思想的引入 . 42 5.2.2 构造过程. 43 5.2.3 原理及理论证明. 44 5.3 仿真实验和分析. 49 5.3.1 各类测量矩阵对二维图像信号的实验结果. 49 5.3.2 各类测量矩阵对一维信号的实验结果. 54 5.4 本章小结. 55 第六章 总结与展望. 56 参考文献. 59 附录 1 攻读硕士学位期间撰写的论文 . 64 附录 2 攻读硕士学位期间参加的科研项目. 65 v 致谢. 66 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章第一章 绪论绪论 1.1 课题研究背景及意义课题研究背景及意义 近年来，信息技术飞速发展，信号处理系统获取数据的能力不断增强，需要采集与处理 的数据量也不断增多，人们对数字信息的需求也随之不断提高。众所周知，依据一般的教材 知识我们就能清楚的知道在对原始连续的模拟信号进行压缩采样时，如果要无失真地从离散 的数字信号中恢复出原始连续的模拟信号，那么信号的采样率必须要大于或等于原始信号频 率的两倍。当然这也是奈奎斯特(nyquist)采样定理的核心内容。因此，在带宽模拟数字化过 程中，往往需要很高的奈奎斯特采样速率，同时又要针对所获取的大量的原始采样信息进行 压缩和传输，这无疑给系统的处理能力以及后续的存储、传输和处理提出了更高的要求，也 给相应的硬件设备的设计带来了巨大的挑战。 既然传统的信息处理框架已经不能满足当前信息技术所提出的条件，因此，寻求某种新 的信号处理方式已成为一种必然。于是，人们自然能联想到，能否建立一种全新的框架，保 证信息无损的同时且能高效重建，用远远低于奈奎斯特采样定理所要求的两倍带宽的采样速 率来对信号进行采样，如果能够将此问题解决，那么，可以大大减小数据处理的代价，显著 地降低时间上的耗费和器件上的成本。 在2006年，donoho和candes12等人在信号逼近和稀疏分解理论的基础之上，提出了一 种称为压缩感知(compressed sensing, cs)的全新信号采样理论，该理论指出：只要用远少于 传统的奈奎斯特采样定理所要求的采样数，就可以精确地或者近似地恢复出原始信号。区别 于传统的奈奎斯特采样定理，压缩感知(compressed sensing)或压缩采样(compressive sampling)34这一全新的理论不是将信号采样和数据压缩这两步分开进行，而是同步进行的， 因此它能有效的减少采样时间和复杂度，节约成本。自从2006年candes和donoho提出压缩感 知这一全新的信号处理理论以来，压缩感知理论在这出现的短短几年之内，一经报道便立即 引起了广泛的关注，是近几年来信号采样领域比较热门的研究课题。目前，学者们已经将压 缩感知这一理论渗透在模拟-信息采样5、雷达成像6、卫星成像7、传感网络8、信源编码 91011、模式识别12、语音压缩13、探地雷达成像14、信道估计15、视频编解码16等一系列 应用领域，它也在这些领域发挥着极其重要的作用。虽然对压缩感知的理论和应用研究还处 在起步阶段，但其展现出的强大生命力受到了国内外许多专家学者的极大关注，成为近几年 来非常热门的研究领域。因此，研究压缩感知理论，不仅在理论领域有着重大意义，而且在 南京邮电大学硕士研究生学位论文 第一章 绪论 2 实践应用领域也有着很大的潜在价值，它很有可能成为未来的一场信号处理的革命。 1.2 本文主要工作和结构安排本文主要工作和结构安排 论文首先简单介绍了压缩感知的研究背景、意义及国内外的研究现状，接着对压缩感知 理论及其两个至关重要的环节即信号重建算法和测量矩阵进行了分类和分析，总结了贪婪算 法中常见的几种算法及其几何模型，并对最近出现的fbp算法进行了一点改进，实验仿真、 分析改进后算法的性能。然后针对传统的sl0算法及其改进算法中正态函数和双曲正切函数 “陡峭性”不大，对于近似 0 l 范数的估计不精确等缺陷，结合sl0算法理论和修正牛顿法、阻 尼牛顿法理论，提出了基于该算法性能更优的优化方法来改进sl0算法，并总结了改进后算 法的步骤，实验仿真、分析算法性能。最后，论文提出一种基于信道编码的压缩感知确定性 测量矩阵的构造方法，进行数据仿真并分析总结。 本论文结构安排及其主要内容如下： 第一章：绪论。本章简单阐述了本文的研究背景、意义并介绍了压缩感知理论在国内外 的发展状况，接着对本文的主要工作和结构安排进行说明。 第二章：压缩感知理论框架。本章首先介绍了压缩感知理论的原理及其数学模型，然后 对压缩感知中常见(三大类)重建算法和(三大类)测量矩阵这两个关键因素进行了简单分析和 总结。 第三章：基于cs理论的图像重构算法。本章主要总结了贪婪算法在原子支撑集计算方法 上的不同，给出几种常见算法的几何模型，比较不同算法的性能，对这些算法进行分析总结 并对fbp算法作了一点改进，对比改进后的fbp算法并进行实验仿真，性能分析。 第四章： 基于sl0压缩感知信号重建的改进算法。 本章针对sl0重建算法及其改进的nsl0 算法存在近似 0 l 范数估计函数和收敛速度两方面的不足，提出一种新的优化算法，并与同类 的贪婪算法和非同类其他算法进行对比研究、matlab实验仿真和数据分析。 第五章：基于信道编码压缩感知测量矩阵的构造方法。本章首先简单介绍了信道编码原 理的相关基础知识，然后结合压缩感知理论中常用传统随机测量矩阵的不足提出一种基于信 道编码的压缩感知确定性测量矩阵构造方法，并进行matlab实验仿真和性能比较。 第六章：总结与展望。对本文所作的研究工作进行总结，针对不足之处提出改进，并对 后续工作进行一系列的展望。 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论框架 3 第二章第二章 压缩感知理论框架压缩感知理论框架 2.1 压缩感知理论简介压缩感知理论简介 压缩感知(compressed sensing, cs)12是近几年信号采样领域出现的一个新兴研究领域。 cs 不同于传统的奈奎斯特/香农(nyquist/shannon)采样定理，它利用了信号的稀疏性和可压 缩性，用一个与变换矩阵不相关的测量矩阵将变换域中的高维信号投影到低维空间上，然后 通过求解一个凸优化问题就能从少量的测量值中以较高概率重建出原始信号。与传统的奈奎 斯特/香农采样的方式相比，cs 减少了重建信号所需要的数据量和信号重建的时间，它在医 学/雷达成像、传感网络、信道/信源编码和无线通信等领域具有广阔的应用前景。 2.2 压缩感知数学模型压缩感知数学模型 压缩感知理论是信号采样领域研究中的一个重要突破。它与传统的信号采样、编解码的 方式有着很大的不同，传统的信号采样、编码、解码的过程如下图 2-1 所示： 图 2-1 传统的编码、解码理论框图 编码端首先对原始信号x进行采样，然后对这些采样值进行变换，将重要系数的幅度和 所在的位置信息进行压缩编码，最终将编码值进行存储或者是传输。信号解码的过程仅仅是 压缩编码的逆过程，即接收到的数据y，经过解压缩和反变换后就能恢复出原始信号 x。 基于这种理论框架对信号进行编、解码的方法存在两个明显的缺陷： (1) 在对原始信号进行采样时，由于采样速率必须大于或者等于信号带宽的 2 倍，使得 硬件系统面临着巨大的挑战； 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论框架 4 (2) 在对采样值进行变换和压缩编码的过程中，经过变换计算得到的那种小的系数通常 被舍弃，这就造成了数值计算上的浪费和在恢复原始信号上的不精确，同时也占用了大量的 内存资源； 科学技术日新月异，人们获取信息的手段也在不断地更新换代，那么获取信息越多，对 信号带宽的要求也会随之增高，进而也对数字信号的处理方式提出了更苛刻的要求。区别于 传统的奈奎斯特采样定理，压缩感知理论的突出优点就是针对可稀疏或可压缩表示的信号， 能将传统的信号采样与数据压缩合二为一， 利用随机投影得到观测值(将高维信号降维到低维 空间)，在信号采样的同时就实现了数据压缩的目的，这样就可以大大减少数据的获取时间和 存储空间。我们在解码端得到很少的测量值，然后通过求解凸优化问题就可以利用这些测量 值以较高概率重建出原始信号。 与传统的编、解码理论框架不同，cs 理论框架如图 2-2 所示： 图 2-2 基于压缩感知理论的编码、解码框图 由图 2-2 可以发现，在 cs 理论中，对原始信号x的采样与数据压缩是在同一步骤且同 一时刻进行的， 以远远低于奈奎斯特/香农(nyquist/shannon)采样率的速率对在某个变换域是 稀疏的或可压缩的信号进行测量，最后得到的测量值y并非是信号本身，这里y只含有信号 的部分信息。解码部分也不再是编码的简单逆过程，而是根据盲源分离的求逆思想，利用信 号重建算法进行信号精确重构，由于常用随机测量矩阵具有其固有的随机性，重建算法能以 比较大的概率来实现信号的精确重构或者带有误差值的近似重构，解码时需要的测量值个数 远远小于传统理论下所需的采样个数。 下面介绍压缩感知理论的三个主要步骤： 第一步：信号的稀疏表示模型 因为cs理论是建立在原始信号具有稀疏性或者可压缩性的基础之上， 这里考虑长度为n 的离散实值信号x，记为 )(nx ， ,.,2 , 1 nn 。假设原始信号在某种变换域下，可以用一组基 n t ,., 21 的线性组合表示(其中 t 为的转置)成： 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论框架 5 n i ii x 1 或者 x (2.1) 这里，是信号x在域的变换向量，xx iii * ,，是大小为nn *的变换矩阵。 当信号x在某个基上仅有nk 个非零系数，则称为信号x的k稀疏基。 信号x在稀疏基上只有k个非零系数 k 时，这是属于严格稀疏的情况。在绝大多数情 况下，信号可能无法满足严格稀疏的要求，但仍具有可压缩性，即变换向量大部分分量的 取值很小，只有少部分分量的取值很大，或者说只要用少部分取值大的分量，就能近似地稀 疏表示原始信号x。 为了使后期信号重建的效率更高，占用的物理资源更少，我们必须要合理的选择稀疏基 ，使稀疏后的信号x的稀疏系数的个数尽量减少。 常用的稀疏基有：正弦(余弦)基、chirplet 基以及 curvelet 基小波基17-21等。 第二步：压缩感知编码模型 在对原始信号进行线性测量时，并不是直接测量信号x本身，而是将信号x投影到一组 测量向量, 21nm 上，得到的测量值 t mm xy,。或者写成矩阵的形式： xy (2.2) 式(2.2)中，x是原始信号， 是1*n维的矩阵，y是测量值， 为1*m维的矩阵， 而是nm * 维的测量矩阵。 将式(2.1)代入到(2.2)中，得到： xy (2.3) 式(2.3)中， 是信息算子，为 nm * 维的矩阵。利用信息算子，从稀疏系数获 取少量的压缩测量值y。 因为测量值y的维数m远远小于原始信号x的维数n，在求解式(2.2)的逆问题时，即由 已知的测量值y去求得原始信号x时，这是一个病态问题，无法直接解出。 而由于式(2.3)中是k稀疏的，只有k个非零系数，满足nmk，那么就可以利用 信号稀疏分解理论中已有的分解算法， 通过求解式(2.3)的逆问题， 得到变换系数， 再将代 回式(2.1)中便可以得到原始信号x。 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论框架 6 candes 等人在文献1-4中提出，cs 理论是建立在信号的稀疏性和非相干性或者稀疏性和 等距约束性的基础之上，这样就保证了算法的收敛性，使k个稀疏系数能够从m个测量值中 准确地恢复出来。 这里，矩阵和矩阵的相干性定义为： |,|max)()( ,1 jk njk n， (2.4) 由文献1-4可知，n)(1，当n)(时，压缩感知测量向量精确重建原始信号 的概率为 0。当 1)( 时，和具有最大的非相干性。且文献1-4中的定理 1 指出，非相 干正交基对 ),( 有利于高效率的压缩采样和信号重建。 而等距约束性(restricted isometry property, rip)22定义如下： 对于任意具有严格k稀疏的向量s，矩阵满足如下不等式： kk s s 1 | | -1 2 2 2 2 (2.5) k 为等距约束常数，且10 k 。 在测量矩阵和稀疏矩阵满足不相干性或者等距约束性时，都可以实现信号的精确或 近似的重建。在实际测量中，稀疏矩阵可能会随着信号的不同而有所改变，因此，希望能 够找到对任意的稀疏基都能满足和测量矩阵不相关。 相关文献49-60指出，常用的测量矩阵有：高斯随机矩阵，贝努利矩阵，部分傅里叶矩阵， 哈达玛矩阵等。这里 rip 准则与测量矩阵和稀疏矩阵满足不相关性的要求是等价的。 第三步：压缩感知解码模型 在 cs 理论中，当式(2.5)中的矩阵满足 rip 准则时，通过求解式(2.3)的逆问题得到稀 疏系数 x t ，然后将代入式(2.1)中，将x求解出来。通过求解问题(2.2)和(2.3)的逆问 题，将n维的原始信号x从m维的观测向量 y 中精确的恢复出来。 定义一个向量 )(,(2),(1),lxxxx 的-l范数为： l l i l i l xx 1 1 )|(| (2.6) 当0l时，得到 0-范数，表示向量x中非零元素的个数。 解决信号的重构问题，最直接的方法是通过转化为 0 l范数最小化的非凸最优化问题，来 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论框架 7 求解式(2.3)的最优化问题： 0 |min l s.t. y (2.7) 从而恢复出稀疏向量，进一步得到原始信号x。 由于 0 l范数的高度非凸性，上式是一个需要组合搜索的不确定多项式(nondeterministic polynomial-hard, np-hard)问题，方程的数量少于要求解的未知数个数，当n很大时，不仅在 数值计算上无法有效地实现，而且抗噪声的能力很差。 文献1-4中指出，通常情况下， 1 l范数最小化问题在一定条件下和 0 l范数最小化问题具有 等价性，可将 0 l范数最小化的非凸优化问题转化为 1 l范数最小化的凸优化问题，也可以得到相 同的解。 因此，问题(2.7)可以转化为 1 l范数最小化凸优化问题： 1 |min l s.t. y (2.8) 在实际求解的过程中，允许一定程度上的误差存在，可将原始的 0 l范数最优化问题转化 为一个比较简单的近似形式求解： 0 |min l s.t. 2 2 |-| y (2.9) 将 1 l范数最小化问题求解模型写成： 1 |min l s.t. 2 2 |-| y (2.10) 或者，在求解上述的 1 l范数最小化的约束优化问题时，可将约束条件转换为惩罚项，构 造非约束优化问题： 2 2 |-| |min 1 y l (2.11) 上式(2.9)(2.10)(2.11)中，是一个极小的常量，而(2.11)中的为 lagrange 乘数， 它控制着信号的稀疏度和重构误差之间的平衡。近年来，学者们也提出了多种重构信号的算 法，主要分为贪婪算法、松弛算法、非凸算法这三类。 2.3 压缩感知重构算法简介压缩感知重构算法简介 压缩感知信号重建的数学模型在理论上存在着无数多个可行解，这是作为欠定的数学反 问题的一个方面。但是，压缩感知的相关定理指出，非相干性或等距约束性准则(rip)为近似 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论框架 8 精确或精确重建原始信号只是提供了理论上的保证。从前述压缩感知的理论或者压缩感知的 数学模型可知，压缩感知的第三个核心问题是信号重建算法的设计。donoho 和 candes 等人 提出重建算法的设计应该遵循如下基本准则： 信号重建算法应该利用尽可能少的压缩测量值， 且能够快速、稳定、高效、精确或近似精确地重建原始信号。简单地说，重建算法主要包括 这三类算法：凸优化算法、贪婪算法法、统计优化算法。 第一类算法：基于l1范数最小的凸优化(松弛)算法 主要包括内点法、lasso、最小角回归(lars)、梯度投影(gpsr)23-27、软/硬迭代阈值 (sit/hit)28等多种稀疏重建算法。总的来说，此类算法是一类计算量大但重建效果相对较好 的算法， 具有重建误差较小， 重建效果较好的特点， 需要的压缩测量个数较少)/log(knko， 并且此类算法计算复杂度相对较高，对于大规模问题难以应用，实用性较差。 第二类算法：基于l0范数最小的贪婪算法 主要包括匹配追踪(mp)29、正交匹配追踪(omp