基于压缩感知理论的重构算法介绍

第一篇：基于压缩感知理论的重构算法介绍

压缩感知重构算法综述

李珅

1,2，马彩文，李艳，陈萍

111（1.中国科学院西安光学精密机械研究所 光电跟踪与测量室,陕西省 西安市 710119;2.中国科学

院研究生院,北京 100039）

摘要：现代社会信息量的激增带来了信号采样、传输和存储的巨大压力，而近年来出现的压缩感知理论(Compressed Sensing,CS)为解决该问题提供了契机。该理论指出：对于稀疏或可压缩的信号，能够以远低于奈奎斯特频率对其进行采样，并通过设计重构算法来精确的恢复该信号。本文介绍了压缩感知理论的基本框架，综述了压缩感知理论的重构算法，其中着重介绍了最优化算法和贪婪算法并比较了各种算法之间的优劣，最后探讨了压缩感知理论重构算法未来的研究重点。

关键词：信号采样;压缩感知;稀疏;重构算法 中图法分类号： TP301.6 文献标识码：A

Survey on reconstruction algorithm based on compressive

sensing

Li Shen1,2, Ma Cai-wen1, Li Yan1, Chen Ping1

(1.Xi’an Institute of Optics and Precision Mechanics of CAS, Xi’an Shaanxi 710119, China；2.Graduate University of Chinese Academy of Sciences, Beijing 100039, China）

Abstract：With the rapid demanding for information, the existing systems are very difficult to meet the challenges of high speed sampling, large volume data transmission and storage.Recently, a new sampling theory called compressive sensing(CS)provides a golden opportunity for solving this problem.CS theory asserts that a signal or image, unknown but supposed to be sparse or compressible in some basis, can be subjected to fewer measurements than traditional methods use, and yet be accurately reconstructed.This paper gives a brief overview of the CS theory framework and reviews the reconstruction algorithm of CS theory.Next, this paper introduces the basis pursuit algorithm and greedy algorithms and explores the difference between them.In the end, we briefly discuss possible implication in the areas of CS data reconstruction.Key words：information sampling;compressive sensing;sparse;reconstruction algorithm

0 引言

随着现代科技的飞速发展，人们对信息量的需求也在剧增。传统的信息采样是基于香农采样定理，它指出信号的采样率不低于最高频率的两倍，信号才能被精确的重构。该理论支配着几乎所有信号的获取、处理、存储和传输。

一方面，在许多实际应用中（如超宽带通信，核磁共振，空间探测，高速AD转换器等），信息在存储和处理时，为达到采样率而需要大量的采样数据，从而导致采样硬件成本昂贵，获取效率低下甚至在某些情况难以实现。另一方面，在数据的存储和传输方面，传统的做法是先按照Nyquist方式获取数据，然后将获得的*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

数据进行压缩，最后将压缩后的数据进行存储或传输。显然，这样的方式造成很大程度的资源浪费，同时也提出了一个问题[1]：既然在压缩中需要丢弃大多数数据，为什么不在采样时直接取得我们需要的重要数据？ 近年来，D.Donoho、E.Candes及华裔科学家T.Tao等人提出了一种新的信息获取理论－压缩感知(Compressive Sensing)，以下简称为CS。该理论指出[1]：对于可压缩的信号，可以通过低于或远低于奈奎斯特标准的方式对其进行数据采样并精确重构该信号。与香农定理不同的是，压缩感知并不是直接测量信号本身，它使用非自适应线性投影（感知矩阵）来获得信号的整体构造从而直接得到重要的信息，忽略那些在有损压缩中会被丢弃的信息。一般来说，压缩感知涉及三个比较重要的层面 [2]：

一、信号稀疏域的选取，是压缩感知理论的基础和前提。

二、观测矩阵的选取，已经证明大部分具有一致分布的随机矩阵都可以作为观测矩阵。

三、重构算法的设计，由于压缩感知采用的是全局非自适应测量方法，观测数量远远少于信号长度，从而数据采集量大大减少。但是需要付出的代价是信号重建算法的软件成本。因此，CS重构算法的好坏直接影响到CS理论是否实用。

其中S是投影系数si,iiT构成的N×1维列向量。显然，X和S是同一个信号的等价表示，其中X是在时域或空间域的表示，S是在Ψ域的表示。当信号可以仅被K个基向量线性表示时，则称信号x为K-稀疏。当K<0有：

sppsii1/pR(2)

传统思路中压缩信号就是采用这种正交变换的方式，其编码解码的策略为：编码首先构造正交基矩阵Ψ，作变换SX,保留S中最重要的K个分量及其对应的位置。解码将K个分量放回到其对应的位置，并将其他位置填0，以此构造Ψ，最后进行反变换S求得重构信号。

显然，这种以Nyquist-Shanon采样定理为准则的编码和解码方法有很多缺点。

一、采样后再进行压缩的方式浪费了大量的采样资源，如果采样后的信号长度仍然很长，那么变换会消耗很长时间；

二、由于需要保留的K个重要分量的位置是随着信号的不同而不同，所以这种编解码方式是自适应的，需要分配多余的存储空间以保留K个重要分量的位置。

三、K个重要分量有可能在传输过程中丢失其中的某几个分量从而造成较差的抗干扰能力。

近几年出现的压缩感知理论，对传统的理念是一次革新，它表明我们可以用比传统途径少得多的采样和测量来恢复信号。该理论主要依赖于两个原则[4]，稀疏（sparsity）和不相关(incoher-ence)，稀疏关于感兴趣的信号，它所表达的意思是：连续时间信号的信息率可能比根据其带宽所建议的小得多，离散时间信号所依赖自由度的T 压缩感知理论简介

1.1基本思想 可压缩（稀疏）的定义：考虑一个一维信号

Nx∈RN×1，都可以用N×1维基向量ii1线性表示。为了简化问题，假设基向量为规范正交向量，使用N×N的基矩阵1|2|...|N,信号x可以被表示为：

xsiii1NorS可以说，许多自然界的(1)

数量比它的长度少得多。

信号在某种程度上都是稀疏的或可压缩的，当以*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

合适的基Ψ来表示时，信号可以有很多简练的表达式。不相关表达了一种含义即以Ψ稀疏表示的信号一定可以在其所需要的域中展开。基于这两个原则，压缩感知理论指出，长度为n的信号X在某组正交基或紧框架nn上的变换系数是稀疏的，如果我们可以用一个与变换基Ψ不相关的观测基Ф（Rmn大多数随机矩阵都满足RIP，如高斯随机测量系和伯努利随机测量系。文献[13]的工作告诉我们：在某种意义上说，选择随机测量对于稀疏矩阵来讲是一种最佳策略，只需要几乎最少的m个测量便可恢复稀疏度为S≤m/log(n/m)的信号，而且分析时所需要的常量都很小。第二类为非相关测量系，即测量矩阵和变换基Ψ是不相关的，其不相关性可以通过测量它们之间的相关系数，文献[14]给出了测量矩阵Ф和变换基Ψ的相关系数μ = N1/2maxi,k|<Ψi, Фi>|，μ越小说明测量矩阵Ф和变换基Ψ的不相关性越大，测量所需要的数目也越少。

第三步：重构信号x，区别于奈奎斯特理论的线性感知问题，由于观测数量m远远小于信号长度n，重构面临着求解一个欠定方程组的问题。当信号x是稀疏或可压缩的，求解欠定方程组的问题可以转化为最小0范数问题如式(4)：，mn）对系数向量进行线性变换，并得到观测集合m1，则可以通过求解最优化问题来精确地重构信号X。

1.2 压缩感知采样过程

基于CS理论实现信号压缩的采样过程为： 第一步：找到某个基或紧框架Ψ，使得信号x在Ψ上是稀疏的，并求出变换系数：S ＝ ΨT X，其中S是X的等价或逼近的稀疏表示。变换基Ψ的选择可以为某种已被广泛应用的基，如小波基、傅里叶基、局部傅里叶基等[5][6]，其中关于正交基的选择，可以参考文献[1]和文献[7]。另外，可以使用紧框架（原子字典）来对信号进行稀疏表示，如曲线波Curvelets[8]和轮廓波Contourlets[9]，这两类变换基具有更好的方向性，并且各向异性，少量系数即可有效地捕捉图像的边缘轮廓，在边缘表示方面优于小波。第二步：需要设计一个平稳的、与变换基Ψ不相关的m×n维观测矩阵Ф，对S进行观测得到观测集合Y=ФS＝ФΨTX，该过程也可以表示为信号x通过矩阵Acs进行非自适应观测：Y=AcsX(其中Acs =ФΨT，称为CS信息算子)。需要关注的问题是观测矩阵Ф的选取，需要保证稀疏向量S从n维降到m维时重要信息不被破坏。在压缩感知理论中，受限等距属性（Restricted Isometry Property, RIP）N[10][11]

minTX0s..tAcsXTXY(4)

然而统计理论和组合优化理论告诉我们，组合优化是一个NP难问题，当N很大时，数值上无法有效实现，且抗噪声能力很差；Candes, Tao和Donoho等人已证明，当测量矩阵满足约束等距性质(Restricted Isometry Property, RIP)时，组合优化问题(或称，l0约束优化问题)可转化为数值上容易处理l1约束的凸优化问题：

minTX1s..tAcsXTXY(5)

除此之外还有一些其它方法可以重构信号,如:1）将l0范数松弛为lp范数；2）通过先验分布引入稀疏性，再用Bayesian方法实现信号稀疏重构；3）使用启发式算法(heuristic algorithms)，如借鉴图模型和编码理论中的belief-propagation和消息传递技术。

是判断矩阵是否可以成为测量矩阵的一个重要的标准。对于k稀疏向量S∈R来说，当它满足式(3)时，测量矩阵Ф满足RIP。

（1-）s2s2（1）s(3)压缩感知理论对于测量系有两个主要的分类：第一类为随机测量系，文献[10][12]已证明压缩感知重构算法研究

2.1 重构算法介绍

*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

现阶段CS重构算法大致可以分为以下几类。

第一类是贪婪迭代算法，针对组合优化问题提出，该类算法主要是将信号与原子字典之间的联系作为测量原子（系数）更加有效或非零的一种方式。基本原则就是通过迭代的方式寻找稀疏向量的支撑集，并且使用受限支撑最小二乘估计来重构信号。这类算法包括：匹配追踪算法(MP ，matching pursuit）、正交匹配追踪算法

[15]

比其他重构算法更优越的重构精度。目前该类算法包括：新期望极大值(Expectation-Maximization, EM)算法[25]、贝叶斯压缩感知(BCS,Bayesian Compressive Sensing)算法[26]、基于单测量向量(SMV，single measurement vector)模型提出的SBL[27](sparse Bayesian Learning)算法和基于多测量向量(MMV，Multiple Measurement Vectors)模型提出的MSBL[28]。SBL是贝叶斯学习中很重要的一类算法，SBLMSBL算法与l1范数凸优化算法不同的是，后者全局最小化通常并不是最稀疏解，而前者的全局最小值则是最稀疏的，并且全局最小值比一些典型的算法（如FOCUSS算法）更少。通过关注时间相关性对现有算法性能的影响，文献[29]提出了AR(autoregressive)-SBL算法，该算法将每一个信号源的建模都作为一次一阶自动回归过程，同时对数据本身进行学习得到AR系数。

(OMP，[16] orthogonal matching pursuit）、分段OMP算法(StOMP，stagewise orthogonal matching pursuit)、规范OMP算法[17](ROMP，Regularized Orthogonal Matching Pursuit)、CoSaMP算法[18](compressive sampling matching pursuit）、迭代硬阈值法

[19](iterative hard thresholding，IHT）以及GraDeS[20](gradient descent with sparsification)等。算法的复杂度大多是由找到正确支撑集所需要的迭代次数决定的，算法计算速度快但是需要的测量数据多且精度低。

第二类是凸优化算法或最优化逼近方法，这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，其中最常用的方法为基础追踪算法（BP，Basic Pursuit），该算法提出使用l1范数替代l0范数来解决最优化问题，以便使用线性编程方法来执行。另一种算法为FOCUSS算法[21]，该算法使用lp范数（p<=1）替代l0范数求解最优化问题。另外，文献[22]还提出了通过极小化l0范数的平滑转换求解问题，称之为SL0方法。该类算法计算速度慢(计算复杂性为N^3)，但需要的测量数据少(O(K*log(N/K))且精度高。另外两种比较常见的凸松弛算法包括GPSR(Gradient Projection for Sparse Reconstruction)算法approximation)算法[24]

[23]

其他算法：这类方法有的要求信号的采样支持通过分组快速测试重建，如傅立叶采样，链式追踪和HHS(Heavg Hitters On Steroids)追踪。有的将贪婪算法和最优化算法相结合，如文献[30]提出的贝叶斯追踪算法(BPA)，算法将简单的贪婪追踪算法和最优化贝叶斯框架相结合，在信号的稀疏表示中找到有效的原子。BPA可以看作是对迭代检测估计(IDE,Iterative Detection Estima-tion)算法的修改。2.2 l1范数凸优化算法

基于l1范数凸优化算法的稀疏重构模型主要有两类[31]：

(LS)minyxxx2s..tx1和

(BPminx1s..t)yx2（6）

SpaRSA(sparse reconstruction by separable。GPSR算法通过使用梯度降的方法求解有界约束最优化问题，算法要求投影在可行域中以确保迭代过程的可行性。第三类算法是基于贝叶斯框架提出的重构算法，该类算法考虑到了信号的时间相关性，特别是当信号具有较强的时间相关性时，能够提供

其中，(LS)式为LASSO(Least Absolute Shrinkage and Selection Operator)问题[32]，(BP)式为基追踪去噪(Basis Pursuit Denoise, BPDN)问题[33], 当没有噪声时，就退化为单一的基追踪(BP)问题[34]。处理实际问题时，通过对系统测量条件的分析，可以得到噪声水平σ的大致估计。相比之下，要先验地估计原信号的l1范*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

数值τ是十分困难的，因此研究(BP)问题的求解更具有实际意义，但是(LS)问题可以作为求解(BP)问题的中间手段。

求解形如(LS)和(BP)的约束优化问题时，可将约束条件转换为惩罚项，构造非约束优化问题。即：

2x冗余的。匹配追踪的任务就是通过每一次匹配把待分析信号f(t)分解成库中一组成员gi(t)(i=1,2,…,N)的线性组合，且N越小越好，实际就是通过对一系列单一原子进行逼近的方法来逐步搜索信号的稀疏解。

匹配跟踪算法虽然简单，但由于它找到的是OMP是恢复稀疏信号算法中较早出现的一类算空间上克服了上述缺陷。

基于压缩感知理论，OMP算法可以通过已知的关于信号的O(mlnd)个随机线性测量来恢复d维空间中的信号。假设S是Rd 空间的k-稀疏信号，Ф为n×d维测量矩阵，列向量为φ1 到φd。数据向量v（v＝Фs）的列是从Ф中选取的某些列的组合。

算法的基本思想源于K-稀疏，是为了找到K个关键的分量，既然是关键，显然它的绝对值应该比其他（N－K）个分量大的多。基于上面的假设，算法就是要从测量矩阵Ф中找到参与信号x测量的列向量。方法是：设置一个剩余向量r和序号集合Λ，在每一次迭代中，从Ф中选出与数据v剩下部分即余量r最相关的那一列，将该列号添加到集合Λ中并从数据v中去掉该列所作的贡献并重新计算余量，直到m次迭代结束。算法最终会得到正确的列序号集合Λ以及数据v的N维近似值am和N维余量rm。需要注意的是，迭代过程中余量rt始终和Фt 的列向量正交。具体的算法可以参考文献[15]。

文献[15]中Tropp和Gilbert分析了OMP算法执行的性能，提出了合适的测量矩阵为N×d维随机矩阵，且具有（M0）独立性、（M1）归一化、（M2）联合相关性和（M3）最小奇异值四个性质。文献[36]也证明了当测量矩阵Ф满足RIP条件时（其中参数k11/(12K)）,OMP算法可通过K个步骤精确地恢复任意K-稀疏信号。同时该文对OMP算法进行了改进，提出了MOMP

逼近结果的稀疏度较差。(QP)minyx2x(7)

次优解，故算法收敛慢、事实上，（QP）问题中的控制参数λ可视为求解约束优化问题(LS)和(BP)中的拉格朗日乘数。因此，若参数σ、λ和τ选取合适，以上三个问题的解是一致的。其中（QP）问题是一个二阶锥规划(second-order cone program)问题，可利用内点法(interior-point)[9,35]求解。

文献[11]比较了各种不同的恢复算法，总结出了l1凸优化算法，如LASSO或BPDN[33,36]

法，通过把信号矢量投影到由选取原子张成的子，通过求解式（8）可以在稀疏计算的复杂度和精度之间提供最佳的平衡点。

minx12yx2x(8)2迭代阈值技术（iterative thresholding algorithm）在稀疏优化算法中经常被采用，一些迭代阈值算法被用在解决LASSO问题上，可以使迭代过程中每一次迭代的计算量减小，这样就可以将LASSO用于解决高维方面的问题[8]。在迭代阈值技术中，迭代收缩算法解决

[20]凸优化问题十分有效，包括IHT [19]、GraDeS、PCD(parallel coordinate descent)以及FISTA(fast-iterative-shrinkage thresholding algorithm)等。对于IHT和GraDes算法，由于该算法使用负梯度作为搜索方向，即Landweber迭代，所以造成算法执行效率偏低。2.3 贪婪算法

MP算法最初是Mallat等人在1993年提出的匹配追踪算法，基本原理就是首先建立一个来分析信号的基本库函数D，不要求库中所有基本函数gi(t)（也叫“原子”）相互正交，但要求其二范数||gi(t)||2=1。因此这组函数并非相互独立，是有*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

（multi-candidate OMP）算法。该算法对OMP的改进在于：在每一次的迭代中，OMP算法只选择一个候选列加入到原子集合中，而MOMP算法选择多个候选列加入到最优原子集合，从而减少迭代的次数，降低重构信号的计算复杂度。文献[34]中，Rauhut研究了使用傅里叶矩阵作为测量矩阵的OMP算法的执行性能，通过大量的试验，他们证明了通过O(Klog(n))个测量就可以精确的恢复K-稀疏信号。同时，Kunis和Rauhut提出，对于m-稀疏信号给出的O（mlnd）次测量，在第一次迭代中，OMP方法可以从测量矩阵中选出正确的列，但是由于矩阵列向量之间存在的微小随机相关性，很难对OMP算法后续的迭代进行分析。于是D.Needell 和 R.Vershynin就在文献[17]中提出了对OMP算法的改进，称为ROMP算法（Regularized Orthogonal Matching Pursuit），该算法可以通过选择替代信号的最大元素并采用正则化的方式来确保没有太多的错误元素被选择，ROMP算法比OMP算法更快速且重构结果更加均衡稳定。文献[37]中Nam H.Nguyen和Trac D.Tran使用ROMP方法从含噪测量中稳定地重构可压缩信号。Donoho也在文献[16]中提出了分段OMP算法(stagewise orthogonal matching pursuit)，该算法对OMP算法进行了简化，通过设置阈值的方法来找到替代的信号，同时以逼近精度为代价进一步提高了计算速度，更适合求解大规模问题。除此之外，2005年Chinh和Minh提出了树型正交匹配算法[38]（TOMP, Tree-based Orthogonal Matching Pursuit），该算法是通过构造稀疏树并在树中追踪重要的系数来实现的。TOMP算法考虑到了信号的多尺度分解时稀疏信号在各奇异子带位置的关系，从而构建了比BP和OMP算法更加快速且重构精度更高的算法。

压缩感知追踪算法（CoSaMP,Compressed Sampling Matching Pursuit）是最近由Needell和Tropp提出的[18]，和大多数贪婪算法一样，CoSaMP算法采用了正交测量矩阵Ф（Ф*TФ近似归一化），因此算法中的替代信号p = Ф*TФS的最大元素与S的非零输入相关联。算法的执行是将p的最大元素加入到运行支撑集中，并使用最小二乘法来获取信号的估计。最后，修正最小二乘估计并更新错误余量。2.4 一些新想法

最近，很多学者提出了一些新想法，其中之一就是将消息传递用于解决压缩感知的信号重构问题。其中，Donoho等提出了一种算法称之为AMP（approximate message passing）[39]，这种算法既具有迭代阈值算法的低复杂度，同时也具备基追踪算法较强的信号重构能力。事实上，AMP是将一些广泛采用的算法集合成的一个实例，是一类新的低复杂度迭代阈值算法，用于解决从较少的线性测量中重构稀疏信号的问题。

考虑式子：

yAS0，S0RN,y,wRn

(9)

其中S0是稀疏向量，ω为噪声。一般的AMP算法的迭代公式如下：

xt10(xtATzt;t)zyAx

ttItnzt(10)

x和z的初始值为x0=0,z0=y，其中，0(x;)(x)sign(x)属于软阈值函数；It 是xt的有效集合。具体的迭代算法和一些相关算法可参见文献[39-44]，这里就不再详述。算法对比及特点评述

BP算法的优势在于它可以当作线性编程问题来解决，因而可以使用标准的技术软件来处理。但是在实际应用中，对于稀疏信号的重构，商业化的软件并不能很好的工作，因为解向量是稀疏的，而测量向量是稠密的，所以即使是常见的图像尺寸，计算也相当耗时且执行复杂度很高。除此之外，由于l1范数无法区分稀疏尺度的位置，所以尽管整体上重构信号在*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

欧氏距离上逼近原信号，但存在低尺度能量搬移到高尺度的现象，从而容易出现一些人工效应，如一维信号会在高频出现振荡。

贪婪算法是CS重构算法中使用比较频繁的一类算法（主要为OMP算法及其改进算法），基本思想是根据残差向量与测量矩阵之间相关性最大的分量，逐步找到原信号的支撑集，并在与信号支撑集相对应的子矩阵上进行类似于最小二乘的计算。该算法较凸优化算法来说，大大提高了计算效率，同时在算法中可以加入额外的先验信息，提高了重构信号的精度。如基于模型的压缩感知方法[45](model based compressed sensing）和前面提到过的贝叶斯压缩感知方法（BCS）。其中BCS算法借助传统的贝叶斯方法与机器学习中的主动学习方法,将关于稀疏性的先验信息用垂直先验分布来建模，提出了自适应的感知方法以及相应的恢复方法。而基于模型的压缩感知方法利用小波树模型和块稀疏模型，仅需要与稀疏程度相当的测量数目即可实现信号的鲁棒性恢复[46]。

当信号稀疏性不是很好且测量中噪声较大时，贪婪算法效果没有凸优化算法好。同时，贪婪算法中涉及到的最小二乘过程要进行矩阵求逆，需大量的矩阵-向量乘法，当算子Φ存在快速算法时也难以应用。近两年，随着梯度投影、迭代阈值等算法的出现，最小l1范数方法的计算效率大幅度提高，同时还可以充分利用算子Φ的快速算法。

CS重构算法各有优缺点，在设计算法时，应根据所应用的领域和信号的特点来进行选择。主要目的是配合CS测量矩阵尽可能减少测量数据并保证重构信号的精度，同时根据需求进行合理权衡。的对于信号重构所采用的最小二乘优化算法已经不够充分，采用不同方式的凸优化算法和贪婪算法来重构信号是压缩感知研究的一个重点。本文对压缩感知理论的框架做了一个简单的描述，着重放在了对压缩感知重构算法的综述上，主要介绍了一些常用的CS重构算法如贪婪算法、凸优化算法等，同时对各算法的特点进行了评述。纵观现在的压缩算法，可以看出今后对于压缩算法的改进主要集中在三个方面：1）构造更稳定、计算复杂度低且需要较少的观测次数的重构算法来精确地恢复可压缩信号；2）构造有效的重构算法来精确恢复含噪信号或在采样过程中被引入噪声的信号；3）将理论与实际相结合，根据特定的领域或应用构造具有针对性的有效可行的压缩算法。参考文献

[1] D L Donoho．Compressed sensing[J].IEEE Transactions on Information Theory.2006,52(4): 1289-1306.[2] 石光明,刘丹华,高大化.压缩感知理论及其研究进展[J].电子学报.2009, 37:1070-1081.[3] Richard G.Baraniuk.Compressive Sensing[J], IEEE Signal Processing Magazine, 2007:118-124.[4] Emmanuel J.Candès, Michael B.Wakin.An Introduction To Compressive Sampling[J].IEEE Signal Processing Magazine,2008,25(2):21-30.[5] I.Daubechies, Ten Lectures on Wavelets.New York:SIAM, 1992.[6] S.Mallat, A Wavelet tour of signal processing, the sparse way, 2009.[7] Emmanuel J.Candès, Justin Romberg, Terence Tao.Stable Signal Recovery from Incomplete and Inaccurate Measurements[J].Communications on Pure and Applied Mathematics, 2006,59(8):1207-1223.[8] E.Cand`es and D.Donoho, New tight frames of curvelets and optimal representations of objects 4 结束语

对于稀疏信号或可压缩信号来说，压缩感知理论作为一种新的信号获取方式，比传统的采样方式更加有效。在压缩感知理论中，传统*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

with piecewise singularities, Comm.Pure Appl.Math.vol.57, pp.219-266, 2004.[9] D.D.-Y.Po and M.N.Do, Directional multiscale modeling of images using the contourlet transform, IEEE Transactions on Image Processing, vol.15(6), pp.1610–1620, 2006.[10] R.Baraniuk, M.Davenport, R.DeVore, and M.Wakin.A simple proof of the restricted isome-try property for random matrices.Constructive Approximation, 2007.[11] E.Cand`es.The restricted isometry property and its implications for compressed sensing.Compte Rendus de l’Academie des Sciences, Paris, 2008.[12] E.Cand`es and T.Tao.Near optimal signal recovery from random projections: Universal encoding strategies.IEEE Transactions on Information Theory, vol.52, pp.5406-5425, 2006.[13] Jérome Bobin, Jean-Luc Starck, Roland Ottensamer.Compressed Sensing in Astronomy[J].IEEE Journal of Selected Topics in Signal Processing, 2008,2(5):718-726 [14] Emmanuel J.Candès.Compressive sampling [A].Proceeding of the International Congress of Mathematicians[C].Madrid, Spain, 2006, 3: 1433-1452.[15] Joel A.Tropp, Anna C.Gilbert.Signal Recovery From Random Measurements Via Orth-ogonal Matching Pursuit[J].IEEE Transactions on Information Theory.2007, 53(12): 4655-4666.[16] D.L.Donoho,Y.Tsaig, I.Drori, and J.L.Starck, “Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit” Stanford Statistics Technical Report 2006-2, 2006.[17] D.Needell and R.Vershynin, “Uniform uncertainty principle and signal recovery via regularized orthogonal matching

pursuit,”

Foundations of Computational Mathematics, vol.9，no.3, pp.317–334, 2009.[18] Needell, D.,Tropp, J.A.CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis, 2009,26(3):301-321.[19] T.Blumensath and M.E.Davies, “Iterative hard thresholding for compressed sensing,” Applied and Computational Harmonic Analysis, vol.27, no.3, pp.265–274, 2009.[20] R.Garg and R.Khandekar, “Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property,” in Proceedings of the 26th International Confer-ence on Machine Learning, pp.337–344, 2009.[21] I.F.Gorodnitski and B.D.Rao, Sparse signal reconstruction from limited data using focuss: a re-weighted norm minimization algorithm[J].IEEE Transactions on Signal Processing, 1997,45(3):600 –616.[22] H.Mohimani, M.Babaie-zadeh, and C.Jutten.A fast approach for overcomplete sparse decomposition based on smoothed l0-norm[J].IEEE Transactions on Signal Processing, 2009, 57(1):289–301.[23] Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[J].IEEE J.Sel.Top.Sign.Proces: Special Issue on Convex Optimization Methods for Signal Processing, 2007,1:586-597.[24] S.J.Wright, R.D.Nowak, and M.A.T.Figueiredo, “Sparse reconstruction by separable approximation,” IEEE Transactions on Signal Processing, vol.57, no.7, pp.2479–2493, 2009.[25] H.Zayyani, M.Babaie-zadeh, C.Jutten.Decoding real-field codes by an iterative expectation-maximizaion algorithm[A].ICASSP [C], 2008, pp.3169–3172.[26] S.Ji, Y.Xue, and L.Carin.Bayesian *基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

compressive sensing[J].IEEE Transactions on Signal Processing, 2008,56(6):2346–2356.[27] D.P.Wipf and B.D.Rao, “Sparse Bayesian learning for basis selection,” IEEE Trans.on Signal Processing, vol.52, no.8, pp.2153–2164, 2004.[28] D.P.Wipf and B.D.Rao, “An empirical Bayesian strategy for solving the simultaneous sparse approximation problem,” IEEE Trans.on Signal Processing, vol.55, no.7, pp.3704–3716, 2007.[29] Z.Zhang and B.D.Rao, “Sparse signal recovery in the presence of correlated multiple measurement vectors,” in Proc.of the 35th International Conference on Acoustics, Speech, and Signal Processing(ICASSP 2010), Texas, USA, 2010, pp.3986–3989.[30] H.Zayyani, M.Babaie-Zadeh, C.Jutten.Bayesian Pursuit Algorithm

for

Sparse Representation[A].IEEE Int.Conf.on Acoustics, Speech, and Signal Processing(ICASSP)[C].Taipei, Taiwan, April 2009.[31] 刘吉英.压缩感知理论及在成像中的应用[D].国防科技技术大学研究生院博士学位论文, 2010 [32] R.Tibshirani.Regression shrinkage and selection via the Lasso[J].J.Roy.Statist.Soc.Ser.B., 1996, 58: 267-288 [33] S.S.Chen, D.L.Donoho, M.A.Saunders.Atomic decomposition by basis pursuit[J].SIAM Rev., 2001, 43: 129-159 [34] S.Kunis, H.Rauhut.Random sampling of sparse trigonometric polynomials ii-orthogonal matching pursuit versus basis pursuit[OL].http://dsp.rice.edu/cs.[35] E.J.Candes.l1-magic[EB/OL].[2011-09-29].http://www.xiexiebang.com

第二篇：VJ压缩算法总结

VJ压缩算法总结

算法介绍

VJ压缩算法是一种适用于串行链路的TCP/IP头压缩算法，对小包有较高的压缩率，可以有效提高串行链路的链路利用率，并有效提高交互式应用的响应速度

算法概述

在一个TCP/IP连接活动期间，在连接上发送的TCP/IP包的包头有大部分信息是保持不变的，这部分信息可以被压缩掉。如果发送方把这部分被压缩掉的信息用一个连接ID来替代，接收方保存上一次收到的TCP/IP包头，则接收方就可以根据存储的信息恢复被压缩掉的数据，链路上的TCP/IP头压缩就得以实现。

算法原理

1.压缩

发送方通过串行链路驱动来发送IP数据报，IP数据报经过压缩器，压缩器检查这个IP数据报是否封装了一个TCP报文段，如果不是就把它标记为TYPE_IP，并封装后发送；否则就在本地存储的一个包头数组中搜索该TCP报文段对应的连接，如果找到，就压缩这个IP数据报，把包头拷贝到查找到的槽位，标记这个包为COMPRESSED_TCP并成帧后发送；如果未找到对应的连接，就把数组中最旧的条目删除，并复制TCP/IP头到这个槽位，同时标记这个包为UNCOMPRESSED_TCP，并发送到对端。UNCOMPRESSED_TCP标记的包没有被压缩，它和正常的IP数据报的唯一区别是其“协议”字段被连接ID替代。连接ID是该TCP/IP数据报头在包头数组中的位置索引。这也是发送法用来同步接受方的方法。接受方收到这个报文后把它按照连接ID存放在数组中，用以解压后续的压缩数据包。

2.解压缩

解压缩器根据收到的不同类型的包做不同的转换：

1）对TYPE_IP类型的包，简单地把它提交给上层协议(IP层)2）对UNCOMPRESSED_TCP类型的包，从IP头的协议类型字段提取出连接ID，并把该字段恢复成IPPROTO_TCP，连接ID被用于在本地数组中存储恢复后的TCP/IP头，连接ID即是该报文头在数组中的索引。

3）对COMPRESSED_TCP类型的包，用包头的连接ID定位到保存的包头，根据存储的包头恢复压缩的数据包头，并用恢复后的包头更新存储的包头。压缩/解压缩的流程如图1所示

图1 SLIP VJ压缩/解压缩算法实现

3.压缩包的格式

被压缩过的TCP/IP报文头部如图2所示：

图2 压缩后的TCP/IP报头

Byte 0 是一个报头变化掩码，用以指示这个报头相对与上一个报头变化的字段，Byte 1是连接标识号，接收方可用它来定位这个连接上一个被存储的报头。Byte 2 – 3是TCP的校验和，接下来就是变化掩码所指定的变化的字段。Delta标示发送的是差值。由于一个连接可能持续较长时间，而在这段时间内，连接标识符是不变的，也可以被压缩掉，C标志位被清除的时候表示连接标识符不变。

算法参考实现

1.压缩器

压缩器对输入的IP包做如下检验：

1)如果四层协议不是TCP，把它标记为TYPE_IP并发送 2)如果分组是IP分片，不做压缩，标记为TYPE_IP并发送

3)如果TCP的SYN, FIN, 或是RST标志被设置或是ACK标志没有设置，则认为该TCP段不可压缩，标记为TYPE_IP并发送

4)通过前3个检查的包将以UNCOMPRESSED_TCP或COMPRESSED_TCP的形式发送

5)如果没有找到对应该报文的连接，则老化一个连接(使用LRU算法)，并存储该报文头，把改报文的协议类型字段替换为连接号，把它作为UNCOMPRESSED_TCP类型的报文发送

6)如果找到了对应该报文的连接，则把存储的包头和当前包头做比较，如果protocol version, header length, type of service, don’t fragment, time-to-live, data offset, IP options和TCP options字段有变化，则发送一个UNCOMPRESSED_TCP类型的报文 7)如果第6步中列举的字段都没有变化，则压缩该TCP/IP报头。

a)如果URG标志被设置，则把紧急指针字段拷入压缩后的报文头，并设置变化掩码的U位。如果URG标志未设置，则比较当前报文头和保存报文头的紧急指针字段，如果有变化，则不压缩当前报文，把它作为UNCOMPRESSED_TCP处理。

b)计算当前报文头和存储报文头窗口字段的差值，如果不为0，在压缩报文中存储该差值，并设置change mask的W位

c)计算TCP确认序列号字段的差值，如果结果小于0或是大于2-1，则不压缩报文，把它作为UNCOMPRESSED_TCP处理，否则，如果结构非0，在压缩报头中记录该差值并设置change mask的A位

d)计算TCP序号之间的差值，如果结果小于0或是大于2-1，则不压缩报文，把它作为UNCOMPRESSED_TCP处理，否则，如果结构非0，在压缩报头中记录该差值并设置change mask的S位

e)U, A, S, W位计算完之后开始检查特殊情况：

 如果U, S和W位都被设置，则不执行压缩，发送一个UNCOMPRESSED_TCP的包。

 如果只有S位被设置，检查序号的改变值是否等于上一个分组中的用户数据长度，如果相等，修改change mask 为SAWU，并丢弃压缩报文中的序号变化值  如果只有S和A被设置，检查它们的变化量是否相等，并等于上一个分组的用户数据长度，如果相等，设这change mask为SWU，并丢弃已计算出的序号和确认序号改变值。

 如果报头没有任何改变，查看该分组是否有用户数据(在这种情况下，这个TCP段可能是一个重复的ACK或是窗口探针)或者前一个分组包含用户数据(在这种

1616情况下这个分组是一个重传的分组)，如果这两种情况中的任何一种出现，发送一个UNCOMPRESSED_TCP类型的分组。

f)计算packet ID字段的差值，如果不是1，设置change mask的I位，并保存差值 g)如果PUSH标志被设置，则设置change mask的P位 h)把当前的TCP/IP报头拷贝到报头数组中 i)在原始报文中用压缩后的报头替换原始报头 j)压缩后的报文传给下层传输

2.解缩压器

解压缩器工作在接收端，它根据压缩器的指示处理压缩报头。解压缩器可能收到4种报文：压缩器产生的3种报文以及由接收器在检测到帧错误时产生的TYPE_ERROR伪报文。解压缩器根据报文的不同类型做不同的处理：

如果是TYPE_ERROR或是未知类型的报文，设置状态中的一个toss标志以丢弃所有COMPRESSED_TCP类型的报文，直到设置C标志的COMPRESSED_TCP类型的报文到达或是UNCOMPRESSED_TCP类型的报文到达。此时不返回任何报文

如果是TYPE_IP类型的报文，不做任何处理，直接返回。

如果是UNCOMPRESSED_TCP类型的报文，检查IP PROTOCOL的连接号字段，如果非法，则设置toss标志，并停止处理；否则清除toss标志，拷贝TCP/IP头到该字段指定的位置，并记录这个连接，恢复IP PROTOCOL字段为TCP(6)并返回这个报文。

如果是COMPRESSED_TCP类型的报文，做如下处理：

 如果change mask 的C位被设置，则检查压缩报头中的connection number字段，如果非法，设置toss标志并停止处理，否则记录这个连接，并清除toss标志  如果change mask 的C标志没有设置，并且toss被置位，丢弃该分组。 把压缩报头的TCP校验和拷贝到存储报头中。

 如果change mask的P标志被置位，则设置存储报头的PUSH标志

 如果change mask的S, A, W, U位都被设置，计算上一个分组用户数据的长度(用存储报头的total length字段减去TCP和IP头的长度)，并加上存储报头的TCP序号字段作为新的TCP序号。

 如果S, W, U位被设置，而A没有设置，则计算上一个TCP段中用户数据的长度，并把它分别加上存储报头的TCP序号和ACK序号作为新的序号。 否则按照压缩器设置的顺序来解释change mask的各个字段

上述过程结束后，重新计算IP的total length（收到的用户数据长度加上存储的TCP/IP报头长度）和IP头校验和，至此完全解压了压缩的TCP/IP头。

第三篇：压缩感知(Compressive Sensing)总结,毕设小节

压缩传感总结报告

摘 要 随着信息技术的不断发展，人们对信息需求量越来越大，这给信号采样、传输和存储的实现带来的压力越来越大。传统的采样方法容易造成信息的冗余，因此，人们寻求新的方法避免信息的冗余。压缩传感的问世，打破了常规的信号处理的思路，它将压缩和采样合并进行，突破了香农采样定理的瓶颈。本文主要围绕稀疏表示、编码测量、重构算法三个方面对压缩传感进行基本的介绍。最后介绍了压缩传感的应用以及展望。

关键词

压缩传感，稀疏表示，编码测量，重构算法 引言

传统的信号获取和处理过程主要包括采样、压缩、传输和解压缩四个部分。其采样过程必须满足香农采样定理, 即采样频率不能低于模拟信号频谱中最高频率的2倍。在信号压缩中,先对信号进行某种变换,如离散余弦变换或小波变换, 然后对少数绝对值较大的系数进行压缩编码, 舍弃零或接近于零的系数。通过对数据进行压缩,舍弃了采样获得的大部分数据, 但不影响“感知效果”[1]。但是，信号压缩实际上是一种严重的资源浪费，因为大量的采样数据在压缩过程中被丢弃了，而它们对于信号来说是不重要的或者只是冗余信息。从这个意义而言，可得到以下结论：带宽不能本质地表达信号的信息，基于信号带宽的Nyquist 采样机制是冗余的或者说是非信息的。

如果信号本身是可压缩的, 那么是否可以直接获取其压缩表示(即压缩数据),从而略去对大量无用信息的采样呢？换句话说，是否存在一种基于信息的采样理论框架，使得采样过程既能保持信号信息，又能只需远少于Nyquist 采样定理所要求的采样数目就可精确或近似精确重建原始信号？Candés在2006年从数学上证明了可以从部分傅立叶变换系数精确重构原始信号, 为压缩传感奠定了理论基础。Candés和Donoho在相关研究基础上于2006年正式提出了压缩传感的概念。其核心思想是将压缩与采样合并进行,首先采集信号的非自适应线性投影(测量值), 然后根据相应重构算法由测量值重构原始信号[7]。

简单地说，压缩感知理论指出：当信号在某个变换域是稀疏的或可压缩的，可以利用与变换矩阵非相干的测量矩阵将变换系数线性投影为低维观测向量，同时这种投影保持了重建信号所需的信息，通过进一步求解稀疏最优化问题就能够从低维观测向量精确地或高概率精确地重建原始高维信号。在该理论框架下，采样速率不再取决于信号的带宽，而在很大程度上取决于两个基本准则：稀疏性和非相干性，或者稀疏性和等距约束性。压缩传感的优点在于信号的投影测量数据量远远小于传统采样方法所获的数据量,突破了香农采样定理的瓶颈,使得高分辨率信号的采集成为可能[2][8]。

压缩传感主要包括以下3个步骤[3]：

(1)长度为N的原始信号x是稀疏的或在基底(NN)下是稀疏的，稀疏信号为；(2)利用观测矩阵(MN)MN获取观测值y(图1，2所示)；(3)已知,和y选择合适的算法恢复x。

图1 x为稀疏信号时的压缩情况

图2 x为非稀疏信号时的压缩情况

由此可知，缩传感理论的研究主要包括信号的稀疏表示、编码测量和重构算法等三个方面。以下做详细介绍。稀疏表示

如果一个信号中只有少数元素是非零的, 则该信号是稀疏的。通常时域内的自然信号都是非稀疏的, 但在某些变换域可能是稀疏的。这就需要采用信号的稀疏表示。信号的稀疏表示就是将信号投影到正交变换基时, 绝大部分变换系数的绝对值很小, 所得到的变换向量是稀疏或者近似稀疏的, 可以将其看作原始信号的一种简洁表达。这是压缩传感的先验条件, 即信号必须在某种变换下可以稀疏表示。

由于一个长度为N的一维离散时间信号, 可以表示为一组标准正交基的线性组合：

Nfxiii1其中，[或fx(1),,]，i12N为列向量,N1的列向量x是f 的加权系数序列，xf,Tf。可见x是信号f 的等价表示，如果x只有很少的大系数, 则称信号f 是iii可压缩的。如果x只有K个元素为非零, 则称x为信号f 的K稀疏表示。

通常变换基可以根据信号本身的特点灵活选取, 常用的有离散余弦变换基、快速傅立叶变换基、离散小波变换基、Curvelets基、Gabor基，当信号不能用正交基稀疏表示时, 可以采用冗余字典稀疏表示。编码测量

M已知长度为N的K稀疏信号x、测量矩阵MN(MN)求测量值y(y)。当x稀疏时可由yx,yix,i得到。当x非稀疏时，首先把x稀疏表示x，然后求测量值yx'。的每一行可以看作是一个传感器（Sensor）,它与信号相乘，拾取了信号的一部分信息。

为了重构信号，Candés和Tao给出并证明了'传感矩阵必须满足约束等距性条件[4]。对于任意K稀疏信号x和常数K(0,1)，如果

(1K)x'x(1K)x(2)

222222成立，则称矩阵'满足约束等距性。Baraniuk给出约束等距性的等价条件是测量矩阵和稀疏表示的基不相关, 即要求的行不能由的列i稀疏表示，且的列i不能由

j的行j稀疏表示。由于是固定的, 要使得'满足约束等距条件，可以通过设计测量矩阵解决。已经证明当是高斯随机矩阵时，传感矩阵'能以较大概率满足约束等距性条件。因此可以通过选择一个大小为MN的高斯测量矩阵得到，其中每一个值都满足N(0,1/N)的独立正态分布。其他常见的能使传感矩阵满足约束等距性的测量矩阵还包括一致球矩阵、二值随机矩阵、局部傅立叶矩阵、局部哈达玛矩阵以及托普利兹矩阵等。信号重构算法

信号重构算法是压缩传感理论的核心，是指由M次测量向量y重构长度为N的稀疏信号x的过程。因为yx，并且y的维数远远低于x的维数，所以方程有无穷多解，无法重构信号。然而如果原始信号是K稀疏的并且测量矩阵满足一定条件，理论证明，信号x可以由测量值y通过求解l0范数问题精确重构：

ˆargminxx0st..xy(3)上式中，为向量的l0范数, 表示向量x 中非零元素的个数。Candés等指出, 如果0要精确重构K稀疏信号x, 测量次数M（即y的维数）必须满足M(Klog(N))。但Donoho指出，最小l0范数问题是一个NP-hard问题。鉴于此，研究人员提出了一系列求得次最优解的算法，主要包括最小l1范数法、匹配追踪系列算法、迭代阈值法以及专门处理二维图像问题的最小全变分法等。

（1）最小l1范数法

采用l1代替l0，得到如下问题：

ˆargminx1stx..xy(4)这是一个凸最优问题, 可以转化成一个线性规划问题加以求解，这种方法也成为基踪方法(Basis Pursuit, BP)。如果考虑重构误差,上述问题可以转换为如下最小l1范数问题：

minxs..txy(5)

12ˆ1，在0点导数不存在，因此梯度对于优化问题，一般采用梯度的方法来求解。而对x算法、矩阵求导等都不好使。必须采用特殊处理，像子梯度（Subgradient）法、平滑近似法（Smooth Approximation）等，但会增加复杂度。

（2）匹配追踪算法

匹配追踪算法(Matching Pursuit, MP)是一种贪婪迭代算法，其基本思想在每一次的迭代过程中,从过完备原子库里(即测量矩阵)选择与信号最匹配的原子来构建稀疏逼近，并求出信号表示残差，然后继续选择与信号残差最为匹配的原子，经过一定次数的迭代，信号可以由一些原子线性表示。但是由于信号在已选定原子(测量矩阵的列向量)集合上的投影的非正交性使得每次迭代的结果可能是次最优的，因此为获得收敛可能需要经过较多次迭代。正交匹配追踪算法(Orthogonal Matching Pursuit，OMP)则有效克服了这个问题，该算法沿用了匹配追踪算法中的原子选择准则，只是通过递归地对已选择原子集合进行正交化以保证迭代的最优性，从而减少了迭代次数。正交匹配追踪算法以极大概率准确重构信号，而且比最小l1范数法更快。但是，正交匹配追踪算法精确重构的理论保证比最小l1范数法弱，并非对所有信号都能准确重构，而且对于测量矩阵的要求比约束等距性更加严格。以下具体讨论OMP算法。

我们知道，恢复原始信号就是找到K个关键分量以及所在的位置。为方便起见，首先假

ˆ就是恢复矩ˆq在xˆ中的对应位置为q。于是'x定K=1，即只有一个非零元素。惟一非零元素xˆ中的非零元素xˆqyq。且yyqˆq的乘积，即'qx阵'的第q列'q与x2/y2。换句

Hy'Hy',s，rq。话说，'的第q 列与y 的相似程度最高，即'q,y'qrr所以，我们只要计算恢复矩阵'的所有列与y的内积，找到内积绝对值最大的那列就行了，H')1Hy，就是使y'xˆq('q该列对应的位置就是q。根据最小二乘法，xqˆq最小qq2ˆq。的那个x这有点像施密特（Schimidt）正交化方法。余量rny'q,y'始终同'q

'q,'qq正交。这也是为什么这个方法叫“正交”匹配追踪的意思了。而匹配，就是找到了最大的',yq。同理，对于K>1，找到余量rn同'中所有列向量最大的那个即可（但第一次找

xˆq2y(',')q2q1xˆq1到的那列要排除，因为它已经保留了下来）。于是，找到使

2最小的那xˆq2个。其中，'q1是第一次找到的那一列，'q2是新找到的那一列（也要记住它的列号ˆxq1xˆq2被更新了，由原来的一个变成两个了，也就是找到两个在变换ˆxq1ˆqq）。可以看出，x2ˆ中对应的位置了。令'q(',')，余量rn又一次被写为：域最关键的元素和其在xq2q1'q,yrny'。继续上面的步骤，直至找到变换域所有K 个最重要的分量[5]。'q,'qqNeedell等在OMP基础上提出了正则正交匹配追踪(Regularized Orthogonal Matching Pursuit, ROMP)算法, 对所有满足约束等距性条件的矩阵和所有稀疏信号都可以准确重构。另外，压缩采样匹配追踪算法(Compressive Sampling Matching Pursuit, CoSaMP)也可以用于很好地重构信号。

除了以上列举的传统的编码与恢复算法以外，还有许多新的关于算法。比如，量化测量压缩传感[9]，贝叶斯压缩传感[10]，扩展图压缩传感[11],比特压缩传感[12]等等。这段时间我主要研究的是基于置信算法的贝叶斯压缩传感[13][14](这部分的内容介绍在PPT上)。压缩传感的应用

压缩传感理论带来了信号采样理论的变革, 具有广阔的应用前景, 包括压缩成像、模拟信息转换、生物传感等。值得注意的是，Rice大学已经成功设计出了一种基于压缩感知的新型单像素相机，在实践中为取代传统相机迈出了实质性的一步。以下主要讨论在通信领域中的应用。

1.雷达成像

压缩传感技术可应用于雷达成像领域，与传统雷达成像技术相比压缩传感雷达成像实现了两个重要改进：在接收端省去脉冲压缩匹配滤波器；同时由于避开了对原始信号的直接采样，降低了接收端对模数转换器件带宽的要求。Bhattacharya等将压缩传感理论应用到合成孔径雷达图像数据获取上, 解决了海量数据采集和存储问题, 显著降低了卫星图像处理的计算代价。

2.信源/信道编码

当原始信号具有稀疏性时，利用压缩采样理论可对其进行有效压缩，减少冗余信息压缩传感理论中关于稀疏性、随机性和凸最优化的结论可以直接应用于设计快速误差校正编码, 这种编码方式在实时传输过程中不受误差的影响。

3．模拟/信息转换

对于带宽非常高的信号，根据香农采样定理，要获得完整的信号信息，所采用的模数转换器必须有很高的采样频率。然而由于传感器及转换硬件性能的限制，获得的信号的带宽远远低于实际信号的带宽，存在较大的信息丢失。利用压缩传感理论首先获得原始信号的线性测量，再利用后端DSP重构原始信号或直接计算原始信号的统计数据等信息。

4.信道估计

把压缩传感应用于OFDM信道估计中，可以在使用较少导频的条件下获得很好的信道估计性能,从而可以提高系统频谱有效性[6]。进一步的工作

压缩传感理论的提出极大地丰富了信号获取理论，并为其他相关领域的研究提供了新技术和新思路，研究前景广阔。然而目前压缩传感理论还不是特别完善，相应的应用研究也刚刚起步, 尚有较多问题需要在未来研究中得到突破： 1）测量矩阵构造研究

在压缩传感中, 测量矩阵需要满足约束等距性条件，目前所采用到的测量矩阵大多为非确定性测量矩阵，但是更复杂的非确定性测量矩阵难以硬件实现，因此有必要对确定性测量矩阵进行深入研究。

2）K、M 和N 三者严格的数学关系尚不明确。当前观测值数目M 与N 和K 的关系较宽松，只是给出了大致范围，其理论下界是否存在是需要研究的问题；另外，由于观测矩阵是随机的，因此信号的精确恢复也是一个概率问题，这个概率与K，M 和N 的具体关系还有待进一步分析。3)由于压缩采样通常处理的是海量数据问题(即N 很大)，已有的多种恢复算法计算复杂度普遍较高，离实际应用还有很大距离。因此，有必要寻找一种低复杂度、实用的高效算法。

参考文献 李树涛, 魏丹.压缩传感综述.自动化学报,2009,35(11):1369-1377.2 邵文泽, 韦志辉, 肖亮等.压缩感知基本理论：回顾与展望.中国科技论文在线.3 金坚, 谷源涛, 梅顺良.压缩采样技术及应用.电子与信息学报,2010,62(2): 470-475 4 Candes E, Tao T.Decoding by linear programming.IEEE Transactions on Information Theory, 2005, 51(12):4203-4215 5 沙威.“压缩传感”引论.http://www.xiexiebang.compressive Sampling.IEEE Signal Processing Magazine,2008,14-20 8 Richard G.Baraniuk.Compressive Sensing.IEEE Signal Process.Magazine,vol.24,pp.118-121,July 2007.9 Argyrios Zymnis, Stephen Boyd, Emmanuel Candes.Compressive Sensing With Quantized Measurements.IEEE Signal Processing Letters,VOL,17,NO.2,2010:149-152 10 S.Ji, Y.Xue,and L.Carin.Bayesian Compressive Sensing.IEEE Trans.Signal.Proc,vol.56,pp.2346-2356 11 Sina Jafarpour, Weiyu Xu, Babak Hassibi,Robert Calderbank.Efficient and Robust Compressed Sensing using Optimized Expander Graphs.IEEE Trans.Inform.Theory, 55(9):4299–4308, September 2009.12 P.Boufounos and R.G.Baraniuk.1-bit Compressive Sensing.In 42ndAnnu.Conf.Information Sciences and Systems(CISS),2008,pp.16-21 13 S.Sarvotham, D.Baron, and R.G.Baraniuk.Compressed Sensing Reconstruction via belief propagation.Rice Univ., Houston,TX,TechREpTrEE601,July.2006.14 D.Baron, S.Sarvotham, and R.G.Baraniuk.Bayesian Compressive Sensing Via Belief Propagation.IEEE Transactions on Signal Processing,VOL.58,NO,1,2020:269-280

第四篇：竹纤维毛巾_压缩毛巾的介绍

压缩毛巾的介绍

压缩毛巾的介绍

一、压缩毛巾的材料：压缩毛巾又称微缩毛巾，是一项全新产品。该产品在以现有毛巾为原料，对其进行二次深加工，使其在不改变原有质量和使用功能的前提下，体积减少80％～90％，使用时遇水膨胀如初，完好无损，从而不仅极大的方便了运输、携带和贮存，而且使毛巾具备了欣赏、馈赠、收藏、礼品、卫生防病等全新的功能，给原毛巾赋予了新的生命力，提高了产品档次，产品试生产投放市场后，受到了广大消费者的热烈欢迎。

二、压缩毛巾的生产：生产压缩毛巾可以说是各纺织企业增加产品品种、提高产品档次的好项目，同时也是其他企业和个人投资办厂创业的一种不错选择。由于该产品具有携带方便、小巧玲珑、新颖别致、干净卫生、防病祛并品种繁多等优点，将会成为人们外出旅游、出差办事的必备佳品。在高档宾馆、桑拿按摩、公共浴池、医院等场所，压缩毛巾可以清除人们对毛巾卫生方面的顾虑。压缩毛巾还可作为小礼物赠送，在产品上印上单位地址、经营范围、风景名胜等就可以作为一件美观大方、新颖别致的纪念品。适用于宾馆、酒店、航空公司、保险公司、交通部门、企事业单位及各旅游公司使用。即使作为工厂发放劳保用品，压缩毛巾由于携带方便、易记数、发放简单、产品新奇等优点也会优于普通毛巾。在人们日常生活中，压缩毛巾也具有广阔的发展前景，压缩毛巾可以设计成各种造型和图案，标新立异，势必引起人们的好奇心，从而引起人们的购买欲望。再者压缩毛巾采用紫外线消毒杀菌，外壳采用先进的PVC封装工艺，使产品不直接与空气接触，从而有效地避免了产品污染，人们可以放心地购买和使用。现在人们对商品的要求越来越高，逐渐从单一的使用功能向多功能、高档次方向转变，而压缩毛巾的问世恰好迎合了这一发展趋势，其市场前景可想而知。

三、压缩毛巾的特点：压缩毛巾又被称为神气毛巾。是采用优质纯棉毛巾经消毒、微缩、封装等工艺加工而成，具有造型多样、设计新颖、体积小、便于携带等特点。使用时，将外包装打开放入水中越10秒种，即可自然膨胀成为常规毛巾。这种压缩毛巾一般都是一次性的，是为了方便出差旅游时携带，可以代替一般的毛巾用，因为是压缩的，所以很方便携带。跟一般的毛巾一样用途。

四、压缩毛巾的神奇：纯棉压缩毛巾，广告文化衫、洗浴巾体恤衫、内裤等产品全部采用先进全自动化生产包装设备，经过高温、高压、消毒等严格的操作程序而制成的新型产品。具有清洁卫生、柔软舒适，吸水性强等特点，是防止交叉感染的最佳选择产品。造型逼真，厚如薄饼、小巧玲珑、便于携带。是理想的环保产品，使用前拆包装后放入水中十秒即可使用，产品可压缩成各种逼真的造型如：圆形、心形、正方形、信用卡形、梅花形、圣诞老人型、汽车型、啤酒瓶等形状....同时还根据客户要求均可在上面及压缩物印制客户指定的彩色广告，产品可作为大型企业、商场、金融、电信等各大公司的广告促销礼品、宾馆用品、纪念品及旅游用品。

武汉学舸纺织品有限公司,专注竹纤维毛巾生产的一家企业，因为专注所以专业

第五篇：理论介绍

弗洛伊德人格理论是一种科学理论。主要包括潜意识与人格理论、本能论、人格发展理论、梦论、焦虑与心理防御机制和社会文化理论。

弗洛伊德认为人格由本我（id）、自我(ego)和超我(superego)构成。

本我（id）

是人格结构中最原始部分，从出生日起算即已存在。构成本我的的成分是人类的基本需求，如饥、渴、性三者均属之。本我中之需求产生时，个体要求立即满足，故而从支配人性的原则言，支配本我的是唯乐原则。例如婴儿每感饥饿时即要求立刻喂奶，决不考虑母亲有无困难。

自我（ego）

是个体出生后，在现实环境中由本我中分化发展而产生，由本我而来的各种需求，如不能在现实中立即获得满足，他就必须迁就现实的限制，并学习到如何在现实中获得需求的满足。从支配人性的原则看，支配自我的是现实原则。此外，自我介于本我与超我之间，对本我的冲动与超我的管制具有缓冲与调节的功能。

超我（superego）

是人格结构中居于管制地位的最高部分，是由于个体在生活中，接受社会文化道德规范的教养而逐渐形成的。超我有两个重要部分：一为自我理想，是要求自己行为符合自己理想的标准；二为良心，是规定自己行为免于犯错的限制。因此，超我是人格结构中的道德部分，从支配人性的原则看，支配超我的是完美原则。

人格结构中的三个层次相互交织，形成一个有机的整体。它们各行其责，分别代表着人格的某一方面：本我反映人的生物本能，按快乐原则行事，是“原始的人”；自我寻求在环境条件允许的条件下让本能冲动能够得到满足，是人格的执行者，按现实原则行事，是“现实的人”；超我追求完美，代表了人的社会性，是“道德的人”。

在通常情况下，本我、自我和超我是处于协调和平衡状态的，从而保证了人格的正常发展。如果三者失调乃至破坏，就会产生心理障碍，危及人格的发展。