基于StOMP算法的压缩感知技术研究.doc

1、 西南交通大学本科毕业设计（论文） 第II页基于步移正交匹配追踪算法的图像压缩感知技术研究 西南交通大学本科毕业设计（论文） 第V页摘 要压缩感知理论是由Donoho和Candes提出的一种充分利用信号稀疏性的全新的信号采样理论。该理论表明，用远低于Nyquist 采样定理要求的频率对信号进行采样也能实现信号的精确重构。压缩感知理论利用原始图像或信号的稀疏性先验知识，通过适当的优化算法，可以由少量的观测值或采样值对信号进行精确重建。该理论突破了传统的以Nyquist定理为基准的信号处理方法，实现了在获取数据的同时对其进行适当的压缩，克服了采样数据量大，采样时间长及数据存储空间浪费严重的问题，因

2、此进一步降低了信号处理的时间和器件成本。 压缩感知理论有三个核心方面：（1）稀疏变换，即对一个非稀疏的信号，找到一个合适的正交基使该信号在它上可以稀疏表示；（2）测量矩阵，与变换基不相干且平稳的矩阵；（3）重构算法，利用数学算法完成对信号的精确重构，该过程可看为求解一个优化问题。 本文研究的主要内容是重构算法，它是压缩感知理论核心中的关键部分，直接决定着重构信号的质量及重构速度、应用效果。重构算法的关键在于如何从压缩感知得到的低维数据中准确地恢复出原始的高维数据。目前看来重构算法主要可以归结为三大类，即贪婪算法，凸优化算法和组合算法。三种算法各有优势，但作为基础算法，贪婪算法中的正交匹配追踪算

3、法对后来陆续提出和改良的算法具有重要的指导意义。 本文通过对压缩感知理论及国内外现有的重建算法进行了学习之后，选择步移正交匹配追踪算法进行重点研究，主要完成工作如下：在总结现有的各种算法及模型如最小L0范数模型，OMP算法，StOMP算法的基础之上，分别从一维信号和二维可压缩信号的角度考察StOMP算法的相对误差、匹配度及运行时间。利用matlab m语言与C语言搭建了仿真平台，对StOMP算法进行了仿真研究。此外对比了几种典型贪婪算法的性能和复杂度。关键词：压缩感知；稀疏变换；匹配追踪；重建算法AbstractCompressed sensing is a novel sampling th

4、eory which is proposed by Donoho and Cands. This theory is under the condition that the signal is compressible or sparse. In this case, using far less than the required sampling frequency of the Nyquist theory to sample the signal is able to accurately reconstruct the signal. For sparse and compress

5、ive signal, it can be reconstructed exactly by using the appropriate reconstruction algorithms. Compressed theory breaks though the traditional Nyquist sampling theory, which overcomes a lot of problems such as a great number of sampling data, time wasting, data storage space wasting and so on. As a

6、 result, it reduces signal processing cost and device cost. The compressed theory has three key sides: (1) Sparse transformation, for a non- sparse signal, we need to find a proper orthogonal basis on which the signal has a sparse representation; (2) Observation matrix, it is irrelevant with the ort

7、hogonal basis; (3) reconstruction algorithms, using a reconstruction algorithm to ensure the accuracy of the signal reconstruction, the whole process can be considered as the solve to a optimization problem. The main content of this thesis is reconstruction algorithm. The key of reconstruction algor

8、ithm is how to accurately recover the original high-dimensional data from low dimensional samples. For now, the reconstruction algorithm can be attributed to three main categories: the greedy algorithm, convex relaxation and the combination algorithm. Three algorithms have their own advantages. As t

9、he basal algorithm, the orthogonal matching pursuit algorithm has important guiding significance for improved and new algorithms. In this thesis, properties of the existing reconstruction algorithms are firstly analyzed. We choose the stagewise orthogonal matching pursuit algorithm as the key resear

10、ch. Based on this, the main contributions of this thesis are summarized as follows. This thesis has reviewed the existing reconstruction algorithms such as L0 minimization, OMP, StOMP and done a large number of experiments on them. The simulation platform based on Matlab m and c language are constru

11、cted. We analyze the results such as PSNR, relative error，matching ratio and running time of these algorithms from one-dimensional sparse signals and two-dimensional compressible signals respectively. Keyword: Compressed sensing; sparse transform; matching pursuit; reconstruction algorithm 目 录摘 要IVA

12、BSTRACTV目 录VI第1章 绪 论11.1 本论文的背景和意义11.2 本论文的主要方法和研究进展11.3 研究背景及意义31.3.1 研究背景31.3.2 研究意义41.4 本论文的结构安排4第2章 压缩感知理论与应用62.1 压缩感知原理62.2 压缩感知主要内容72.2.1 信号的稀疏变换72.2.2 测量矩阵82.2.3 信号的重构102.3 压缩感知的应用102.3.1 压缩成像112.3.2 信道编码112.3.3 模拟/信息转换122.3.4 生物传感12第三章 压缩感知重构算法133.1 最小L1范数法133.2 匹配追踪算法143.3 最小全变分法143.4 迭代阈值法

13、15第四章 STOMP算法164.1 STOMP算法及其实现164.1.1 StOMP算法步骤164.1.2 StOMP算法的Matlab语言实现174.1.3 StOMP算法的C语言实现184.1.4 Matlab与C的混合编程194.2 StOMP算法的仿真与结果分析224.2.1 不同采样率下的仿真结果224.2.2 不同阈值下的仿真结果254.2.3 加噪情况下的仿真结果274.2.4 算法性能分析30结 论345.1 全文总结345.2 工作的的不足与展望34致 谢36参考文献37 西南交通大学本科毕业设计（论文） 第38页第1章 绪 论1.1 本论文的背景和意义众所周知，传统的信号

14、采样以奈奎斯特（Nyquist）采样定理为基础。为了不丢失信号的信息，精确重构信号，在获取信号时，采样频率要大于信号中最高频率的两倍。但是随着各种信号处理系统获取能力的不断增强，需要后期处理的数据量也快速增加，奈奎斯特定理的局限性给系统的处理能力提出了更高的要求，同时也给相应的硬件设施的设计带来了极大的挑战。如何高效处理这些数据并且最大限度的节省存储空间及传输成本已成为目前信息领域进一步向前发展的主要瓶颈之一。 实际上，奈奎斯特采样定理是信号精确重构的充分条件而不是必要条件，奈奎斯特采样定理并不是唯一、最优的采样理论。因此研究如何突破以奈奎斯特采样定理为基础的信息的提取、处理、融合、存储、及传

15、输是推动信息领域发展的关键。 在2004年Donoho等人针对稀疏性信号，提出了压缩感知（Compressive sensing,简称CS）理论。在随后的几年间该理论迅速发展，为解决上述问题奠定了基础。与传统信号处理方式不同，压缩感知理论以空间变换为基础，随机观测矩阵作为手段，优化求解作为恢复信号的方法。压缩感知理论在获取信号的同时对数据进行适当的压缩，其采样频率低于奈奎斯特采样频率，减少了采样数据，节省了存储空间，同时又包含了足够的信息量，能通过合适的重建算法对特定的图像或者信号进行精确重构。它将传统的数据采集和压缩合二为一，并且不需要复杂的数据编码算法，非常适合于要求采用小型器件的实现场合

16、。信号的稀疏重建与压缩感知理论有重大的实用价值和应用前景，已经成为信号领域中一个新的研究方向。1.2 本论文的主要方法和研究进展从2004年提出压缩感知理论至今，该理论得到了飞速的发展。现有的压缩感知理论的研究成果大多来自于外国的学者，国内对于压缩感知的研究还处于起步阶段。作为一个新的理论，有关压缩感知的学术论文还主要在于理论上的证明和完善。目前，压缩感知理论在信号重建优化问题求解，稀疏变换及采样观测矩阵的设计方面取得了一定的进展。 在信号重构方面，目前常用的重构算法主要是以下两大类，即针对最小L0范数提出的一系列贪婪算法及由最小L1范数提出的凸优化算法。 凸优化算法的计算量大但是重建效果较好

17、，它主要针对最小L1范数进行求解。其求解模型主要为 s.t. (1-1)或者将上式转化为无约束问题 (1-2)其中，是松弛因子，它控制着重建误差和信号稀疏度之间的平衡。这一类算法主要有梯度投影法（GPSK, Gradient Projection for Sparse Reconstruction）、基追踪算法（BP， Basis Pursuit）、最小角度回归法（LARS，Least Angle Regression）、同伦算法（Homotopy Algorithm）等。凸优化算法重构误差小，重构效果较好，但是这类算法的复杂度高，对于大规模数据问题难以应用，实用性较差。 相比而言，由于计算量

18、小，重建效果较好且较容易实现，贪婪算法的应用最为广泛。这类算法是针对最小L0范数进行求解，它允许一定的重构误差存在，求解模型如下 s.t. (1-3)其中为一个很小的常数。这类算法的代表是匹配追踪（MP, Matching Pursuit）算法1和正交匹配追踪（OMP，Orthogonal Matching Pursuit）算法2。此外还包括基于OMP算法的一系列改进算法主要包括正则化匹配追踪（ROMP，Regularize OMP）、步移正交匹配追踪（StOMP，stagewise orthogonal matching pursuit）、稀疏自适应匹配追踪（SAMP， Sparse Ada

19、ptive MP）、压缩采样匹配追踪法（CoSaMP， Compressed Sampling MP）等。Blumensath和Davie提出了针对贪婪算法的方向追踪法（DP， Directional Pursuit），这类算法在选取合适的原子之后不采用耗时的最小二乘法求解，通过选择合适的方向和步长来搜索最优解，这种方式比最小二乘法求解要快很多，其搜索方向通常采取负梯度，共轭梯度方向等。这类算法有梯度追踪（GP， Gradient Pursuit）、共轭梯度追踪（CGP，Conjugate GP）等。梯度追踪算法在压缩感知中的信号重构过程中应用到最优化理论中的快速下降法，并且结合了匹配追踪算法

20、，在计算量上尽量逼近MP算法，在重建效果上逼近OMP算法，这是一种可行的信号重建算法。 最近，Rath和Gulllemot提出了一种新的解决方法，弥补空间匹配追踪（CMP， Complementary MP）。以上介绍的算法都是通过M维的观测信号y和观测矩阵来求解N维的原始信号x,而CMP算法则是直接在原始信号x所在的N维空间中求解。这种求解方式不仅收敛速度快，信号的重构质量好，而且重构出的信号更加稀疏。 另外还有Byesian类得统计优化算法，最小（0p1）范数的迭代聚焦算法（FOCUSS， Focal Underdetermined System Solver）等，这些方法的性能介于贪婪算

21、法和凸优化算法之间。 迭代阈值法（ISA, Iterative threshold algorithm）在实际中也得到了广泛的应用，这类算法较易实现，计算量适中，在最小L1范数的贪婪算法和最小L1范数的凸优化算法中都有应用。但是迭代阈值算法对于迭代初值和阈值的选取都比较敏感，而且不能保证求出的解是稀疏的。 由于压缩感知理论有着广泛的应用前景，接下来的工作便是相关理论的完善和实践应用的成果，理论上包括图像视频压缩、信号恢复、分布式压缩感知理论、超宽带雷达系统、医学影像系统和光谱图像处理等方面。在硬件实现上，美国的Rice大学已研制出了单像素相机，它具备传统成像器件不具有的对图像波长的自适应能力。

22、1.3 研究背景及意义1.3.1 研究背景传统的信号获取，编译码过程如图1-1所示：信号X变换压缩解码采样编 Y码端恢复信号X解压缩反变换解 接受数据码 端 Y 图1-1 传统信号采集、编码过程 Figure 1-1 Traditional signal acquisition，encoding process编码端先对信号进行采样，然后对所有的采样值进行变换，压缩编码，即将其中重要数据的幅度和位置进行编码，再将编码值进行储存或者传输。解码端是编码的逆过程，接收到的信号经解压缩、反变换之后得到恢复信号。这种传统的以奈奎斯特定理为基础的编译码方式存在两个缺陷：（1）数据的获取及处理，在实际的应用

23、中，例如超宽带通信、核磁共振、空间探测等，信号的采样率不得低于信号最大带宽的两倍，这对硬件系统的要求很高，奈奎斯特采样硬件成本昂贵，而且获取数据的效率低下，甚至在某些情况下无法实现；（2）数据的存储及传输，传统的做法是先按那奎斯特采样定理获取数据，然后再将得到的数据进行压缩，最后再进行存储或传输。显然，这样的方式会造成很大的资源浪费。另外，为保证信息的安全传输，通常的加密技术是用某种方式对信号进行编码，这给信息的安全传输和接受带来一定程度的麻烦。 由上可知，奈奎斯特理论并不是最优的采样理论，因此研究如何突破以奈奎斯特定理为基础的传统信息处理方式是推动信息领域发展的关键。为了突破奈奎斯特采样定理

24、的限制已经发展了一些理论，典型的例子有Landau理论，Papoulis等的非均匀采样理论，M. Vetterli等的 finite rate of innovation信号采样理论等。近年来，由D. Donoho、E. Cands及T. Tao等人提出了一种新的信息获取理论即压缩感知（Compressive Sensing(CS) or Compressed sensing、Compressed sampling）。该理论指出：对可压缩的信号可通过远低于奈奎斯采样频率进行采样数据，仍能够精确地恢复出原始信号。即在信号获取的过程中用最少的系数来表述信号，并可以在需要时通过适当的重构算法将足够的

25、数据点从压缩传感数据中恢复出来。1.3.2 研究意义作为压缩感知理论的核心之一，对推动压缩感知理论的进一步发展重构算法的研究有着举足轻重的作用，没有重构算法压缩感知理论就毫无意义，更无从谈起相较于奈奎斯特采样定理的优势。截至目前，众多国内外学者先后在重建算法领域做出了新的研究和探索。虽然现有的算法能较好的重构出信号，但是都存在着固有的缺点，对目前的主流的两种算法而言，基于最小L1范数的重建算法计算量大，无法应用于大规模信号；虽然贪婪算法重构速度快，但是在信号重构质量上还需提高。因此，找寻能兼顾信号重构质量和重建时间的算法是目前急需解决的问题之一，这也是将重构算法从理论仿真推向实际应用的关键。另

26、外，有些算法虽然能够重构出信号，但是缺乏理论支撑，这需要很高的数学理论基础，这对研究者的能力提出了更高的要求。其次鲁棒性差、对含噪信号的重构效果差也是现有重构算法的缺陷。因此有关压缩感知重构算法的研究还有很多值得进一步探索和研究的地方。1.4 本论文的结构安排本文主要是针对压缩感知信号重构算法中的贪婪算法进行研究，因为在实际应用中贪婪算法比凸优化算法更有意义，而且贪婪算法在大多数场合下都能满足信号重建的质量要求，甚至一些贪婪算法的重构质量优于凸优化算法。本文在对压缩感知理论以及现有的重构算法进行系统的研究之后，围绕匹配追踪的重建算法展开研究，给出了一种优化的重构算法即步移正交匹配追踪算法。基于

27、上述工作，本文内容分为五章，具体结构安排如下：第一章：绪论。首先介绍了压缩感知理论的研究背景及意义，然后介绍了国内外研究背景和现状，最后整理出全文内容的结构安排。第二章：压缩感知理论与应用。首先介绍了压缩感知的原理，进而对信号的稀疏变换、传感矩阵的设计以及信号的重构三个主要方面的内容展开进一步详述，最后详细介绍了压缩感知理论在不同领域的应用。第三章：基于压缩感知理论的信号重构算法。这一章对现有的三类主要信号重构算法进行综合概述，着重分析了正交匹配追踪算法和最小L1范数算法等的原理，内容及性质。第四章：StOMP算法。首先介绍了StOMP算法的思想以及算法步骤，然后再matlab上进行试验仿真，

28、得出实验数据。进而再用C语言实现算法比较不同的实现方式之间的差异。最后将StOMP算法与其他算法进行比较研究做出总结分析。第五章：总结与展望。对全文的工作进行了总结，提出本文不足的地方，展望这一领域的进一步研究方向。第2章 压缩感知理论与应用2.1 压缩感知原理压缩感知是一种利用信号的稀疏性或者可压缩性对其进行重构的技术。压缩感知的突出优点是对于可稀疏表示的信号能将数据的获取和压缩合二为一，大大减少了数据的获取时间及存储空间。数字信号x(n)模拟信号x(t)系数s(n)数字信号y(m) AIC 图2-1 压缩感知过程 Figure 2-1 Compressive Sensing图2-2是一个压

29、缩感知过程。它包括压缩感知过程和信号稀疏重构过程。不同于传统的奈奎斯特采样，压缩感知的核心是线性测量过程。设x为长度为N的由传统采样得到的信号，通过压缩感知可直接得到长度为M的测量信号y （其中MN），它们的关系为 (2-1) 其中称为传感矩阵或者测量矩阵，大小为M*N。 当x为可压缩信号时，在正交稀疏变换下可通过稀疏s表示，记为 (2-2)其中s为K-稀疏的即只有K个非零元素，于是测量过程可记为 (2-3)其中是大小为M*N的矩阵。压缩感知测量过程如图2-2所示。 图2-2 压缩感知的测量过程 Figure 2-2 the Measuring Process of CS通过压缩感知我们得到，

30、其中观测矩阵大小为M*N。从信号y中会恢复出原始信号x的过程称为基于压缩感知的稀疏重建，由于测量矩阵维数M远小于原始信号维数N，求解（2-1）的逆问题是一个NP难问题，所以我们不能直接从y的M维测量值中求解出N维原始信号x。问题（2-2）中s是K-稀疏的，而且，因此可将原始目标函数近似等价为 s.t. (2-4)这将无法求解的NP难组合最优化问题转化成了求解线性规划最优化问题。得到原始信号x在域内的稀疏形式s，由正交变换的可逆性可容易地从s中恢复信号x。Cands等人在文献3中指出，为了确保算法的收敛性，能用M个测量值准确地恢复K个系数，那么式（2-2）中的测量矩阵必须满足限制等容性（Rest

31、ricted Isometry property，RIP），即对任意K-稀疏的矢量，矩阵都能满足下列不等式 (2-5)其中。测量矩阵和稀疏矩阵满足不相关性的要求是RIP准则的一种等价情况3。2.2 压缩感知主要内容压缩感知理论体系主要包括三个核心方面：（1）对于信号，需要找到一个合适的正交基，是信号x能在上得到稀疏表示，即信号的稀疏分解；（2）设计一个与正交基不相关的平稳测量矩阵；（3）设计一个合适的重建算法，用来精确地恢复原始信号。2.2.1 信号的稀疏变换用压缩感知理论进行信号处理的前提是信号在某个特定的正交基上必须具有稀疏性，信号的稀疏性和所选的正交基特性密切相关。对于一个特定的信号，需

32、要选择一个合适的稀疏变换域，使信号能有最好的稀疏表示。假设是一维离散信号组成的列向量，那么任意一组N维向量都可以用一个N*1维的向量基表示，假设这个向量基正交，那么通过矩阵，信号X可表示为： ， 即 (2-6)其中，和X是N*1维的矩阵，是N*N维矩阵，若中只有K（KL）个非零元素（或者取其较大的值），其他的N-K个系数全为零（或者取值很小），那么称X是K-稀疏的，是信号X的稀疏基。实际情况下，信号不能严格满足稀疏的条件，即信号在稀疏域中仅有K个非零系数。我们只能选择一个适当的稀疏基，使信号的稀疏系数个数最大限度的减小，以此来提高信号采集速度，降低存储空间占用率，并且保证恢复信号的精度。在研究

33、信号的稀疏变换时，可以通过稀疏系数的衰减速度来衡量变换基稀疏表示的能力。Cands和Tao4研究表明，具有幂次衰减速度的信号可以利用压缩感知理论来恢复。文献4中指出光滑信号的傅里叶系数、小波系数、振荡信号的Gabor系数及具有不连续边缘的图像信号的Curvelet系数等都具有良好的稀疏性，通过压缩感知理论可较好的恢复出信号。如何寻求适合一类信号的正交基，得到信号的最佳稀疏表示，是有待进一步研究的问题。G. Peyr将变换基是正交基这一条件扩展为由多个正交基构成的正交基字典。在某个正交基字典中，可自适应地寻找能逼近某一信号特征的最佳正交基，稀疏变换后能得到最稀疏的信号表示。近几年，出现了一种新的

34、信号表示的理论即在冗余字典下对信号进行稀疏分解。字典的选择尽可能的符合被逼近信号的特性，但字典的构成可以没有任何限制。从冗余字典中寻找具有最佳线性组合的一系列原子来表示目标信号，这称作信号的稀疏逼近或者高度非线性逼近5。从非线性逼近角度来看，信号的稀疏逼近包括两方面：（1）根据目标信号从给定的基库中选择出最佳基；（2）从最佳基中选出最佳的K项组合。这种方法的稳定性较好，而且复杂度较低。2.2.2 测量矩阵由压缩感知整个过程可看出，测量矩阵起着至关重要的作用。测量矩阵的选择关系到能否实现信号的压缩，以及信号能否被精确重构。2007年Cands6等研究者提出了著名的Restricted Isome

35、try Principle（RIP）理论，即假定向量信号x长度为N，稀疏度为K，测量矩阵为，大小为M*N。向量集合，其中T的元素个数小于或等于稀疏度K，即。矩阵表示测量矩阵中由向量集合T中元素所对应的列向量组成的子矩阵，大小为M*|T|。若存在常数，使下列不等式成立 (2-7)则我们称测量矩阵具有K阶RIP性质。其中常数的定义详见文献7。由此可知，只要测量矩阵（不一定是随机矩阵，可以是确定的矩阵）满足RIP条件，则K*log（N/K）的采样值就能将N维信号的K个非零（或较大值）稳定的重建出来，限制等容性的等价条件为测量矩阵和稀疏矩阵不相关，即的行值不能由的列稀疏表示，而且的列不能用的行表示。虽

36、然 RIP理论特性很好，但是很难用它来判断某个测量矩阵（部分高斯随机测量矩阵，傅里叶测量矩阵除外）是否有这样的特性，而且很难用这一理论来指导设计测量矩阵。此外，RIP是设计测量矩阵的充分条件，而非必要条件。Donoho在文献3中提出压缩感知理论的同时定性且定量的给出了测量矩阵需要满足的三个条件：（1）由测量矩阵的部分列向量构成的子矩阵的最小奇异值要大于一定的常数，即测量矩阵的列向量要有一定的线性独立性；（2）测量矩阵的列向量有一定的类似噪声的独立随机性；（3）稀疏解是满足L-范数最小的向量。这对测量向量的设计起着重要的作用。完成测量矩阵的硬件实现是压缩感知理论应用于实际的必备条件。在RIP特性

37、的指导下，RICE大学研制出了单像素相机,而后，许多硬件实现的报道相继而来，例如麻省理工学院研制的编码孔径相机、MRI RF脉冲设备，中科院研制的压缩感知混沌器和滤波器等。这些硬件的实现推动了压缩感知的进一步应用。由上可知，构造合适的测量矩阵时应尽量符合以下要求8：（1）在稀疏度K相同的条件下。采样值M越小越好；（2）硬件和优化算法实现简单；（3）通用性好，即对大多数可压缩或稀疏信号均适用。根据以上测量矩阵的性质和所需满足的条件，目前提出了三大类测量矩阵。第一类测量矩阵包括高斯随机矩阵1、亚高斯随机测量矩阵、伯努利随机测量矩阵1、非稀疏投影矩阵等，这一类矩阵的元素独立地服从某一分布，它们与大多

38、数稀疏或可压缩信号不相关，精确重建时所需的测量数较小。但是这些测量矩阵需要较大的空间来存储，而且计算复杂度较高。其中高斯矩阵和伯努利矩阵公式如下：高斯随机矩阵 (2-8)伯努利随机测量矩阵 (2-9)式（2-7）和（2-8）中，其中为过采样因子，N为原始信号长度，K为稀疏度。第二类测量矩阵包括部分傅里叶矩阵6、部分非相关测量矩阵和哈达玛矩阵。这些矩阵从一个大小为N*N的正交矩阵中随机选取M行，然后对每一列进行归一化处理后得到。傅里叶测量矩阵充分利用了快速傅里叶变换计算速度快的特点，但是它仅与在频域或时域稀疏的信号不相关。而哈达玛测量矩阵的大小N必须满足，这极大的限制了它的应用。第三类矩阵包括T

39、oeplitz矩阵和Circulant矩阵,二进制稀疏（Binary Sparse）矩阵，Chirps矩阵，随机卷积形成的感知矩阵等。这类矩阵部分是根据某一特定信号应用的矩阵，如Chirps测量矩阵是由Chirps序列组成感知矩阵的列向量。上述测量矩阵都有一定的优势，但是它们有一个共同点，即大部分是随机测量矩阵。随机矩阵有一些缺点。首先在仿真中存在不确定性，为了研究这类测量矩阵的性质，需要用大量的实验数据求平均来消除不确定性。其次，随机矩阵在硬件中难以实现。因此，确定性测量矩阵成为测量矩阵新的研究方向。2.2.3 信号的重构 信号的重构是压缩感知理论中最为关键的一部分，当随机测量矩阵满足RIP

40、准则时，可以通过对式（2-3）求逆得到稀疏系数，然后将其代入（2-2）中将K-稀疏的原始信号x从M维的测量数据中精确恢复出来。假定一个向量的L-范数为： (2-10)当l=0时即得到0-范数，代表向量X中的非零项个数。信号重构时最直接的方法是在范数下进行求解，即 s.t (2-11)由于基于范数的优化问题是一个NP-hard问题，它的计算量很大但是无法直接求解。从数学角度来看，这和稀疏分解问题很相似，因此现有的稀疏分解算法可直接应用于信号重构中。通常，我们将其转化为求解范数，这将非凸优化问题转化为一个凸优化问题即： s.t. (2-12)最小范数解具有唯一性和稳定性。常用的算法有基追踪（Bas

41、is Pursuit，BP）算法、梯度投影法（Gradient Projection For Sparse, GPSK ）、凸集交替投影法（Projections onto Convex sets, POCS）、内点迭代法等。但是最小化范数并重构稀疏信号的唯一方法，还有其他方法例如贪婪算法和组合算法。贪婪算法用每次迭代过程中得到的局部最优解来完成对原始信号的不断逼近，此类算法包括匹配追踪算法、正交匹配追踪算法以及基于此的改进算法。它在正交方向上寻找非零系数，能提高算法的收敛速度。它的衍生算法也有很多，但都是基于匹配追踪里的原子匹配准则，在性能上都有不同程度上网提高。而组合算法对原始信号的采样能

42、进行快速的分组测试重建，它适用于大规模数据的问题，但是重构速度不稳定有时很快。2.3 压缩感知的应用压缩感知理论带来了信号处理领域的变革，有着广阔的应用前景，如雷达成像、压缩成像、无线传感器网络、模拟信息转换、生物传感等9。 2.3.1 压缩成像在获取数据方面，RICE大学成功的研制出了一种单像素照相机10，如图2-3。这种相机通过光路系统将成像的目标投影到一个数字微镜器（Digital Micromirror Device，DMD ）上，它的反射光由透镜聚焦到光敏二极管上。光敏二极管两边的电压值就是一个测量矩阵y，把这个投影重复操作M次，即可得到测量向量y，再用最小全变分算法构造的信号处理器

43、重构出原始信号f。数字微反射镜通过数字电压信号来控制微镜片的机械运动，以此来调整入射光线，相当于随机测量矩阵。因为这个相机直接得到M次随机线性测量值，没有获取原始信号的N（MN）个像素值，这使低像素相机拍摄高像素图像成为可能。 图2-3 单像素CS相机 Figure 2-3 Mono-pixel camera压缩感知技术也可用于雷达成像领域。与传统的雷达成像技术相比压缩感知雷达成像有了两个重要的改进。首先在接收端略去了脉冲压缩匹配滤波器，其次降低了接收端对模数转换器的带宽要求。设计的重点从传统设计的昂贵接收端硬件转换为设计新的信号重构算法，因此简化了雷达成像系统10。Bhattacharya等

44、人将压缩感知理论应用到合成孔径雷达图像数据的获取上，这解决了大量数据获取和存取的问题，大大降低了卫星图像处理的计算代价。除此之外，压缩感知技术也可用于医学成像领域，例如压缩感知三维磁共振波谱成像、稀疏核磁共振成像等。 2.3.2 信道编码压缩感知理论中有关稀疏性、凸最优化和随机性的结论可直接应用在设计快速误差校正编码中。这使得信号在实时传输过程中不受误差的影响11。在压缩编码过程中，对于编码器而言稀疏表示所需的基可能是未知的。但是在压缩感知编码过程中，只在译码和重构原始信号是需要稀疏基，因此不需要它的结构特性，即可以用通用的编码策略来编码。Haupt等人通过实验指出若图像是高度可压缩或SNR值足够大，即使测量过程中存在噪声，压缩感知方法也可以精确重构图像；Marcia以及Stankovic分别研究了压缩视频编码孔径的重建和视频压缩采样的问题；Cevher等利用原始图像与背景图像稀疏的性质，做背景抽取，这可以直接对图像中的目标成像。为了解决高维图像重构算法慢的问题，Gan提出了基于块的压缩感知技术等。2.3.3 模拟/信息转换对于宽带大的信号，比如雷达和通信信号处理系统中的射频信号，由香农定理可知，要得到完整的原始信号信息，模数转换器