第一篇：基于壓縮感知理論的重構算法介紹

壓縮感知重構算法綜述

李珅

1,2，馬彩文，李艷，陳萍

111（1.中國科學院西安光學精密機械研究所 光電跟蹤與測量室,陜西省 西安市 710119;2.中國科學

院研究生院,北京 100039）

摘要：現代社會信息量的激增帶來了信號采樣、傳輸和存儲的巨大壓力，而近年來出現的壓縮感知理論(Compressed Sensing,CS)為解決該問題提供了契機。該理論指出：對于稀疏或可壓縮的信號，能夠以遠低于奈奎斯特頻率對其進行采樣，并通過設計重構算法來精確的恢復該信號。本文介紹了壓縮感知理論的基本框架，綜述了壓縮感知理論的重構算法，其中著重介紹了最優(yōu)化算法和貪婪算法并比較了各種算法之間的優(yōu)劣，最后探討了壓縮感知理論重構算法未來的研究重點。

關鍵詞：信號采樣;壓縮感知;稀疏;重構算法 中圖法分類號： 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 引言

隨著現代科技的飛速發(fā)展，人們對信息量的需求也在劇增。傳統的信息采樣是基于香農采樣定理，它指出信號的采樣率不低于最高頻率的兩倍，信號才能被精確的重構。該理論支配著幾乎所有信號的獲取、處理、存儲和傳輸。

一方面，在許多實際應用中（如超寬帶通信，核磁共振，空間探測，高速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)，稀疏關于感興趣的信號，它所表達的意思是：連續(xù)時間信號的信息率可能比根據其帶寬所建議的小得多，離散時間信號所依賴自由度的T 壓縮感知理論簡介

1.1基本思想 可壓縮（稀疏）的定義：考慮一個一維信號

Nx∈RN×1，都可以用N×1維基向量??i?i?1線性表示。為了簡化問題，假設基向量為規(guī)范正交向量，使用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，區(qū)別于奈奎斯特理論的線性感知問題，由于觀測數量m遠遠小于信號長度n，重構面臨著求解一個欠定方程組的問題。當信號x是稀疏或可壓縮的，求解欠定方程組的問題可以轉化為最小0范數問題如式(4)：，m??n）對系數向量進行線性變換，并得到觀測集合?m?1，則可以通過求解最優(yōu)化問題來精確地重構信號X。

1.2 壓縮感知采樣過程

基于CS理論實現信號壓縮的采樣過程為： 第一步：找到某個基或緊框架Ψ，使得信號x在Ψ上是稀疏的，并求出變換系數：S ＝ ΨT X，其中S是X的等價或逼近的稀疏表示。變換基Ψ的選擇可以為某種已被廣泛應用的基，如小波基、傅里葉基、局部傅里葉基等[5][6]，其中關于正交基的選擇，可以參考文獻[1]和文獻[7]。另外，可以使用緊框架（原子字典）來對信號進行稀疏表示，如曲線波Curvelets[8]和輪廓波Contourlets[9]，這兩類變換基具有更好的方向性，并且各向異性，少量系數即可有效地捕捉圖像的邊緣輪廓，在邊緣表示方面優(yōu)于小波。第二步：需要設計一個平穩(wěn)的、與變換基Ψ不相關的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)

然而統計理論和組合優(yōu)化理論告訴我們，組合優(yōu)化是一個NP難問題，當N很大時，數值上無法有效實現，且抗噪聲能力很差；Candes, Tao和Donoho等人已證明，當測量矩陣?滿足約束等距性質(Restricted Isometry Property, RIP)時，組合優(yōu)化問題(或稱，l0約束優(yōu)化問題)可轉化為數值上容易處理l1約束的凸優(yōu)化問題：

min?TX1s..tAcsX???TX?Y(5)

除此之外還有一些其它方法可以重構信號,如:1）將l0范數松弛為lp范數；2）通過先驗分布引入稀疏性，再用Bayesian方法實現信號稀疏重構；3）使用啟發(fā)式算法(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重構算法大致可以分為以下幾類。

第一類是貪婪迭代算法，針對組合優(yōu)化問題提出，該類算法主要是將信號與原子字典之間的聯系作為測量原子（系數）更加有效或非零的一種方式?；驹瓌t就是通過迭代的方式尋找稀疏向量的支撐集，并且使用受限支撐最小二乘估計來重構信號。這類算法包括：匹配追蹤算法(MP ，matching pursuit）、正交匹配追蹤算法

[15]

比其他重構算法更優(yōu)越的重構精度。目前該類算法包括：新期望極大值(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范數凸優(yōu)化算法不同的是，后者全局最小化通常并不是最稀疏解，而前者的全局最小值則是最稀疏的，并且全局最小值比一些典型的算法（如FOCUSS算法）更少。通過關注時間相關性對現有算法性能的影響，文獻[29]提出了AR(autoregressive)-SBL算法，該算法將每一個信號源的建模都作為一次一階自動回歸過程，同時對數據本身進行學習得到AR系數。

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

[19](iterative hard thresholding，IHT）以及GraDeS[20](gradient descent with sparsification)等。算法的復雜度大多是由找到正確支撐集所需要的迭代次數決定的，算法計算速度快但是需要的測量數據多且精度低。

第二類是凸優(yōu)化算法或最優(yōu)化逼近方法，這類方法通過將非凸問題轉化為凸問題求解找到信號的逼近，其中最常用的方法為基礎追蹤算法（BP，Basic Pursuit），該算法提出使用l1范數替代l0范數來解決最優(yōu)化問題，以便使用線性編程方法來執(zhí)行。另一種算法為FOCUSS算法[21]，該算法使用lp范數（p<=1）替代l0范數求解最優(yōu)化問題。另外，文獻[22]還提出了通過極小化l0范數的平滑轉換求解問題，稱之為SL0方法。該類算法計算速度慢(計算復雜性為N^3)，但需要的測量數據少(O(K*log(N/K))且精度高。另外兩種比較常見的凸松弛算法包括GPSR(Gradient Projection for Sparse Reconstruction)算法approximation)算法[24]

[23]

其他算法：這類方法有的要求信號的采樣支持通過分組快速測試重建，如傅立葉采樣，鏈式追蹤和HHS(Heavg Hitters On Steroids)追蹤。有的將貪婪算法和最優(yōu)化算法相結合，如文獻[30]提出的貝葉斯追蹤算法(BPA)，算法將簡單的貪婪追蹤算法和最優(yōu)化貝葉斯框架相結合，在信號的稀疏表示中找到有效的原子。BPA可以看作是對迭代檢測估計(IDE,Iterative Detection Estima-tion)算法的修改。2.2 l1范數凸優(yōu)化算法

基于l1范數凸優(yōu)化算法的稀疏重構模型主要有兩類[31]：

(LS?)miny??xxx2s..tx??1和

(BPminx1s..t?)y??x??2（6）

SpaRSA(sparse reconstruction by separable。GPSR算法通過使用梯度降的方法求解有界約束最優(yōu)化問題，算法要求投影在可行域中以確保迭代過程的可行性。第三類算法是基于貝葉斯框架提出的重構算法，該類算法考慮到了信號的時間相關性，特別是當信號具有較強的時間相關性時，能夠提供

其中，(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?)的約束優(yōu)化問題時，可將約束條件轉換為懲罰項，構造非約束優(yōu)化問題。即：

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）個分量大的多?；谏厦娴募僭O，算法就是要從測量矩陣Ф中找到參與信號x測量的列向量。方法是：設置一個剩余向量r和序號集合Λ，在每一次迭代中，從Ф中選出與數據v剩下部分即余量r最相關的那一列，將該列號添加到集合Λ中并從數據v中去掉該列所作的貢獻并重新計算余量，直到m次迭代結束。算法最終會得到正確的列序號集合Λ以及數據v的N維近似值am和N維余量rm。需要注意的是，迭代過程中余量rt始終和Фt 的列向量正交。具體的算法可以參考文獻[15]。

文獻[15]中Tropp和Gilbert分析了OMP算法執(zhí)行的性能，提出了合適的測量矩陣為N×d維隨機矩陣，且具有（M0）獨立性、（M1）歸一化、（M2）聯合相關性和（M3）最小奇異值四個性質。文獻[36]也證明了當測量矩陣Ф滿足RIP條件時（其中參數?k?1?1/(1?2K)）,OMP算法可通過K個步驟精確地恢復任意K-稀疏信號。同時該文對OMP算法進行了改進，提出了MOMP

逼近結果的稀疏度較差。(QP?)miny??x2??x(7)

次優(yōu)解，故算法收斂慢、事實上，（QP?）問題中的控制參數λ可視為求解約束優(yōu)化問題(LS?)和(BP?)中的拉格朗日乘數。因此，若參數σ、λ和τ選取合適，以上三個問題的解是一致的。其中（QP?）問題是一個二階錐規(guī)劃(second-order cone program)問題，可利用內點法(interior-point)[9,35]求解。

文獻[11]比較了各種不同的恢復算法，總結出了l1凸優(yōu)化算法，如LASSO或BPDN[33,36]

法，通過把信號矢量投影到由選取原子張成的子，通過求解式（8）可以在稀疏計算的復雜度和精度之間提供最佳的平衡點。

minx12y??x2??x(8)2迭代閾值技術（iterative thresholding algorithm）在稀疏優(yōu)化算法中經常被采用，一些迭代閾值算法被用在解決LASSO問題上，可以使迭代過程中每一次迭代的計算量減小，這樣就可以將LASSO用于解決高維方面的問題[8]。在迭代閾值技術中，迭代收縮算法解決

[20]凸優(yōu)化問題十分有效，包括IHT [19]、GraDeS、PCD(parallel coordinate descent)以及FISTA(fast-iterative-shrinkage thresholding algorithm)等。對于IHT和GraDes算法，由于該算法使用負梯度作為搜索方向，即Landweber迭代，所以造成算法執(zhí)行效率偏低。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算法選擇多個候選列加入到最優(yōu)原子集合，從而減少迭代的次數，降低重構信號的計算復雜度。文獻[34]中，Rauhut研究了使用傅里葉矩陣作為測量矩陣的OMP算法的執(zhí)行性能，通過大量的試驗，他們證明了通過O(Klog(n))個測量就可以精確的恢復K-稀疏信號。同時，Kunis和Rauhut提出，對于m-稀疏信號給出的O（mlnd）次測量，在第一次迭代中，OMP方法可以從測量矩陣中選出正確的列，但是由于矩陣列向量之間存在的微小隨機相關性，很難對OMP算法后續(xù)的迭代進行分析。于是D.Needell 和 R.Vershynin就在文獻[17]中提出了對OMP算法的改進，稱為ROMP算法（Regularized Orthogonal Matching Pursuit），該算法可以通過選擇替代信號的最大元素并采用正則化的方式來確保沒有太多的錯誤元素被選擇，ROMP算法比OMP算法更快速且重構結果更加均衡穩(wěn)定。文獻[37]中Nam H.Nguyen和Trac D.Tran使用ROMP方法從含噪測量中穩(wěn)定地重構可壓縮信號。Donoho也在文獻[16]中提出了分段OMP算法(stagewise orthogonal matching pursuit)，該算法對OMP算法進行了簡化，通過設置閾值的方法來找到替代的信號，同時以逼近精度為代價進一步提高了計算速度，更適合求解大規(guī)模問題。除此之外，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的非零輸入相關聯。算法的執(zhí)行是將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算法的優(yōu)勢在于它可以當作線性編程問題來解決，因而可以使用標準的技術軟件來處理。但是在實際應用中，對于稀疏信號的重構，商業(yè)化的軟件并不能很好的工作，因為解向量是稀疏的，而測量向量是稠密的，所以即使是常見的圖像尺寸，計算也相當耗時且執(zhí)行復雜度很高。除此之外，由于l1范數無法區(qū)分稀疏尺度的位置，所以盡管整體上重構信號在*基金項目：陜西省自然科學基金資助項目（2012JM8021）作者簡介：李珅（1980—），女，河北樂亭人，在讀博士，主要從事壓縮感知和圖像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

歐氏距離上逼近原信號，但存在低尺度能量搬移到高尺度的現象，從而容易出現一些人工效應，如一維信號會在高頻出現振蕩。

貪婪算法是CS重構算法中使用比較頻繁的一類算法（主要為OMP算法及其改進算法），基本思想是根據殘差向量與測量矩陣之間相關性最大的分量，逐步找到原信號的支撐集，并在與信號支撐集相對應的子矩陣上進行類似于最小二乘的計算。該算法較凸優(yōu)化算法來說，大大提高了計算效率，同時在算法中可以加入額外的先驗信息，提高了重構信號的精度。如基于模型的壓縮感知方法[45](model based compressed sensing）和前面提到過的貝葉斯壓縮感知方法（BCS）。其中BCS算法借助傳統的貝葉斯方法與機器學習中的主動學習方法,將關于稀疏性的先驗信息用垂直先驗分布來建模，提出了自適應的感知方法以及相應的恢復方法。而基于模型的壓縮感知方法利用小波樹模型和塊稀疏模型，僅需要與稀疏程度相當的測量數目即可實現信號的魯棒性恢復[46]。

當信號稀疏性不是很好且測量中噪聲較大時，貪婪算法效果沒有凸優(yōu)化算法好。同時，貪婪算法中涉及到的最小二乘過程要進行矩陣求逆，需大量的矩陣-向量乘法，當算子Φ存在快速算法時也難以應用。近兩年，隨著梯度投影、迭代閾值等算法的出現，最小l1范數方法的計算效率大幅度提高，同時還可以充分利用算子Φ的快速算法。

CS重構算法各有優(yōu)缺點，在設計算法時，應根據所應用的領域和信號的特點來進行選擇。主要目的是配合CS測量矩陣盡可能減少測量數據并保證重構信號的精度，同時根據需求進行合理權衡。的對于信號重構所采用的最小二乘優(yōu)化算法已經不夠充分，采用不同方式的凸優(yōu)化算法和貪婪算法來重構信號是壓縮感知研究的一個重點。本文對壓縮感知理論的框架做了一個簡單的描述，著重放在了對壓縮感知重構算法的綜述上，主要介紹了一些常用的CS重構算法如貪婪算法、凸優(yōu)化算法等，同時對各算法的特點進行了評述?？v觀現在的壓縮算法，可以看出今后對于壓縮算法的改進主要集中在三個方面：1）構造更穩(wěn)定、計算復雜度低且需要較少的觀測次數的重構算法來精確地恢復可壓縮信號；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://004km.cn

第二篇：VJ壓縮算法總結

VJ壓縮算法總結

算法介紹

VJ壓縮算法是一種適用于串行鏈路的TCP/IP頭壓縮算法，對小包有較高的壓縮率，可以有效提高串行鏈路的鏈路利用率，并有效提高交互式應用的響應速度

算法概述

在一個TCP/IP連接活動期間，在連接上發(fā)送的TCP/IP包的包頭有大部分信息是保持不變的，這部分信息可以被壓縮掉。如果發(fā)送方把這部分被壓縮掉的信息用一個連接ID來替代，接收方保存上一次收到的TCP/IP包頭，則接收方就可以根據存儲的信息恢復被壓縮掉的數據，鏈路上的TCP/IP頭壓縮就得以實現。

算法原理

1.壓縮

發(fā)送方通過串行鏈路驅動來發(fā)送IP數據報，IP數據報經過壓縮器，壓縮器檢查這個IP數據報是否封裝了一個TCP報文段，如果不是就把它標記為TYPE_IP，并封裝后發(fā)送；否則就在本地存儲的一個包頭數組中搜索該TCP報文段對應的連接，如果找到，就壓縮這個IP數據報，把包頭拷貝到查找到的槽位，標記這個包為COMPRESSED_TCP并成幀后發(fā)送；如果未找到對應的連接，就把數組中最舊的條目刪除，并復制TCP/IP頭到這個槽位，同時標記這個包為UNCOMPRESSED_TCP，并發(fā)送到對端。UNCOMPRESSED_TCP標記的包沒有被壓縮，它和正常的IP數據報的唯一區(qū)別是其“協議”字段被連接ID替代。連接ID是該TCP/IP數據報頭在包頭數組中的位置索引。這也是發(fā)送法用來同步接受方的方法。接受方收到這個報文后把它按照連接ID存放在數組中，用以解壓后續(xù)的壓縮數據包。

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標示發(fā)送的是差值。由于一個連接可能持續(xù)較長時間，而在這段時間內，連接標識符是不變的，也可以被壓縮掉，C標志位被清除的時候表示連接標識符不變。

算法參考實現

1.壓縮器

壓縮器對輸入的IP包做如下檢驗：

1)如果四層協議不是TCP，把它標記為TYPE_IP并發(fā)送 2)如果分組是IP分片，不做壓縮，標記為TYPE_IP并發(fā)送

3)如果TCP的SYN, FIN, 或是RST標志被設置或是ACK標志沒有設置，則認為該TCP段不可壓縮，標記為TYPE_IP并發(fā)送

4)通過前3個檢查的包將以UNCOMPRESSED_TCP或COMPRESSED_TCP的形式發(fā)送

5)如果沒有找到對應該報文的連接，則老化一個連接(使用LRU算法)，并存儲該報文頭，把改報文的協議類型字段替換為連接號，把它作為UNCOMPRESSED_TCP類型的報文發(fā)送

6)如果找到了對應該報文的連接，則把存儲的包頭和當前包頭做比較，如果protocol version, header length, type of service, don’t fragment, time-to-live, data offset, IP options和TCP options字段有變化，則發(fā)送一個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位都被設置，則不執(zhí)行壓縮，發(fā)送一個UNCOMPRESSED_TCP的包。

? 如果只有S位被設置，檢查序號的改變值是否等于上一個分組中的用戶數據長度，如果相等，修改change mask 為SAWU，并丟棄壓縮報文中的序號變化值 ? 如果只有S和A被設置，檢查它們的變化量是否相等，并等于上一個分組的用戶數據長度，如果相等，設這change mask為SWU，并丟棄已計算出的序號和確認序號改變值。

? 如果報頭沒有任何改變，查看該分組是否有用戶數據(在這種情況下，這個TCP段可能是一個重復的ACK或是窗口探針)或者前一個分組包含用戶數據(在這種

1616情況下這個分組是一個重傳的分組)，如果這兩種情況中的任何一種出現，發(fā)送一個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或是未知類型的報文，設置狀態(tài)中的一個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)總結,畢設小節(jié)

壓縮傳感總結報告

摘 要 隨著信息技術的不斷發(fā)展，人們對信息需求量越來越大，這給信號采樣、傳輸和存儲的實現帶來的壓力越來越大。傳統的采樣方法容易造成信息的冗余，因此，人們尋求新的方法避免信息的冗余。壓縮傳感的問世，打破了常規(guī)的信號處理的思路，它將壓縮和采樣合并進行，突破了香農采樣定理的瓶頸。本文主要圍繞稀疏表示、編碼測量、重構算法三個方面對壓縮傳感進行基本的介紹。最后介紹了壓縮傳感的應用以及展望。

關鍵詞

壓縮傳感，稀疏表示，編碼測量，重構算法 引言

傳統的信號獲取和處理過程主要包括采樣、壓縮、傳輸和解壓縮四個部分。其采樣過程必須滿足香農采樣定理, 即采樣頻率不能低于模擬信號頻譜中最高頻率的2倍。在信號壓縮中,先對信號進行某種變換,如離散余弦變換或小波變換, 然后對少數絕對值較大的系數進行壓縮編碼, 舍棄零或接近于零的系數。通過對數據進行壓縮,舍棄了采樣獲得的大部分數據, 但不影響“感知效果”[1]。但是，信號壓縮實際上是一種嚴重的資源浪費，因為大量的采樣數據在壓縮過程中被丟棄了，而它們對于信號來說是不重要的或者只是冗余信息。從這個意義而言，可得到以下結論：帶寬不能本質地表達信號的信息，基于信號帶寬的Nyquist 采樣機制是冗余的或者說是非信息的。

如果信號本身是可壓縮的, 那么是否可以直接獲取其壓縮表示(即壓縮數據),從而略去對大量無用信息的采樣呢？換句話說，是否存在一種基于信息的采樣理論框架，使得采樣過程既能保持信號信息，又能只需遠少于Nyquist 采樣定理所要求的采樣數目就可精確或近似精確重建原始信號？Candés在2006年從數學上證明了可以從部分傅立葉變換系數精確重構原始信號, 為壓縮傳感奠定了理論基礎。Candés和Donoho在相關研究基礎上于2006年正式提出了壓縮傳感的概念。其核心思想是將壓縮與采樣合并進行,首先采集信號的非自適應線性投影(測量值), 然后根據相應重構算法由測量值重構原始信號[7]。

簡單地說，壓縮感知理論指出：當信號在某個變換域是稀疏的或可壓縮的，可以利用與變換矩陣非相干的測量矩陣將變換系數線性投影為低維觀測向量，同時這種投影保持了重建信號所需的信息，通過進一步求解稀疏最優(yōu)化問題就能夠從低維觀測向量精確地或高概率精確地重建原始高維信號。在該理論框架下，采樣速率不再取決于信號的帶寬，而在很大程度上取決于兩個基本準則：稀疏性和非相干性，或者稀疏性和等距約束性。壓縮傳感的優(yōu)點在于信號的投影測量數據量遠遠小于傳統采樣方法所獲的數據量,突破了香農采樣定理的瓶頸,使得高分辨率信號的采集成為可能[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)的獨立正態(tài)分布。其他常見的能使傳感矩陣滿足約束等距性的測量矩陣還包括一致球矩陣、二值隨機矩陣、局部傅立葉矩陣、局部哈達瑪矩陣以及托普利茲矩陣等。信號重構算法

信號重構算法是壓縮傳感理論的核心，是指由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問題。鑒于此，研究人員提出了一系列求得次最優(yōu)解的算法，主要包括最小l1范數法、匹配追蹤系列算法、迭代閾值法以及專門處理二維圖像問題的最小全變分法等。

（1）最小l1范數法

采用l1代替l0，得到如下問題：

??argminx1stx..?x?y(4)這是一個凸最優(yōu)問題, 可以轉化成一個線性規(guī)劃問題加以求解，這種方法也成為基蹤方法(Basis Pursuit, BP)。如果考慮重構誤差,上述問題可以轉換為如下最小l1范數問題：

minxs..t?x?y??(5)

12?1，在0點導數不存在，因此梯度對于優(yōu)化問題，一般采用梯度的方法來求解。而對x算法、矩陣求導等都不好使。必須采用特殊處理，像子梯度（Subgradient）法、平滑近似法（Smooth Approximation）等，但會增加復雜度。

（2）匹配追蹤算法

匹配追蹤算法(Matching Pursuit, MP)是一種貪婪迭代算法，其基本思想在每一次的迭代過程中,從過完備原子庫里(即測量矩陣?)選擇與信號最匹配的原子來構建稀疏逼近，并求出信號表示殘差，然后繼續(xù)選擇與信號殘差最為匹配的原子，經過一定次數的迭代，信號可以由一些原子線性表示。但是由于信號在已選定原子(測量矩陣的列向量)集合上的投影的非正交性使得每次迭代的結果可能是次最優(yōu)的，因此為獲得收斂可能需要經過較多次迭代。正交匹配追蹤算法(Orthogonal Matching Pursuit，OMP)則有效克服了這個問題，該算法沿用了匹配追蹤算法中的原子選擇準則，只是通過遞歸地對已選擇原子集合進行正交化以保證迭代的最優(yōu)性，從而減少了迭代次數。正交匹配追蹤算法以極大概率準確重構信號，而且比最小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??'。繼續(xù)上面的步驟，直至找到變換域所有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等將壓縮傳感理論應用到合成孔徑雷達圖像數據獲取上, 解決了海量數據采集和存儲問題, 顯著降低了衛(wèi)星圖像處理的計算代價。

2.信源/信道編碼

當原始信號具有稀疏性時，利用壓縮采樣理論可對其進行有效壓縮，減少冗余信息壓縮傳感理論中關于稀疏性、隨機性和凸最優(yōu)化的結論可以直接應用于設計快速誤差校正編碼, 這種編碼方式在實時傳輸過程中不受誤差的影響。

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://004km.cnpressive 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％，使用時遇水膨脹如初，完好無損，從而不僅極大的方便了運輸、攜帶和貯存，而且使毛巾具備了欣賞、饋贈、收藏、禮品、衛(wèi)生防病等全新的功能，給原毛巾賦予了新的生命力，提高了產品檔次，產品試生產投放市場后，受到了廣大消費者的熱烈歡迎。

二、壓縮毛巾的生產：生產壓縮毛巾可以說是各紡織企業(yè)增加產品品種、提高產品檔次的好項目，同時也是其他企業(yè)和個人投資辦廠創(chuàng)業(yè)的一種不錯選擇。由于該產品具有攜帶方便、小巧玲瓏、新穎別致、干凈衛(wèi)生、防病祛并品種繁多等優(yōu)點，將會成為人們外出旅游、出差辦事的必備佳品。在高檔賓館、桑拿按摩、公共浴池、醫(yī)院等場所，壓縮毛巾可以清除人們對毛巾衛(wèi)生方面的顧慮。壓縮毛巾還可作為小禮物贈送，在產品上印上單位地址、經營范圍、風景名勝等就可以作為一件美觀大方、新穎別致的紀念品。適用于賓館、酒店、航空公司、保險公司、交通部門、企事業(yè)單位及各旅游公司使用。即使作為工廠發(fā)放勞保用品，壓縮毛巾由于攜帶方便、易記數、發(fā)放簡單、產品新奇等優(yōu)點也會優(yōu)于普通毛巾。在人們日常生活中，壓縮毛巾也具有廣闊的發(fā)展前景，壓縮毛巾可以設計成各種造型和圖案，標新立異，勢必引起人們的好奇心，從而引起人們的購買欲望。再者壓縮毛巾采用紫外線消毒殺菌，外殼采用先進的PVC封裝工藝，使產品不直接與空氣接觸，從而有效地避免了產品污染，人們可以放心地購買和使用?，F在人們對商品的要求越來越高，逐漸從單一的使用功能向多功能、高檔次方向轉變，而壓縮毛巾的問世恰好迎合了這一發(fā)展趨勢，其市場前景可想而知。

三、壓縮毛巾的特點：壓縮毛巾又被稱為神氣毛巾。是采用優(yōu)質純棉毛巾經消毒、微縮、封裝等工藝加工而成，具有造型多樣、設計新穎、體積小、便于攜帶等特點。使用時，將外包裝打開放入水中越10秒種，即可自然膨脹成為常規(guī)毛巾。這種壓縮毛巾一般都是一次性的，是為了方便出差旅游時攜帶，可以代替一般的毛巾用，因為是壓縮的，所以很方便攜帶。跟一般的毛巾一樣用途。

四、壓縮毛巾的神奇：純棉壓縮毛巾，廣告文化衫、洗浴巾體恤衫、內褲等產品全部采用先進全自動化生產包裝設備，經過高溫、高壓、消毒等嚴格的操作程序而制成的新型產品。具有清潔衛(wèi)生、柔軟舒適，吸水性強等特點，是防止交叉感染的最佳選擇產品。造型逼真，厚如薄餅、小巧玲瓏、便于攜帶。是理想的環(huán)保產品，使用前拆包裝后放入水中十秒即可使用，產品可壓縮成各種逼真的造型如：圓形、心形、正方形、信用卡形、梅花形、圣誕老人型、汽車型、啤酒瓶等形狀....同時還根據客戶要求均可在上面及壓縮物印制客戶指定的彩色廣告，產品可作為大型企業(yè)、商場、金融、電信等各大公司的廣告促銷禮品、賓館用品、紀念品及旅游用品。

武漢學舸紡織品有限公司,專注竹纖維毛巾生產的一家企業(yè)，因為專注所以專業(yè)

第五篇：理論介紹

弗洛伊德人格理論是一種科學理論。主要包括潛意識與人格理論、本能論、人格發(fā)展理論、夢論、焦慮與心理防御機制和社會文化理論。

弗洛伊德認為人格由本我（id）、自我(ego)和超我(superego)構成。

本我（id）

是人格結構中最原始部分，從出生日起算即已存在。構成本我的的成分是人類的基本需求，如饑、渴、性三者均屬之。本我中之需求產生時，個體要求立即滿足，故而從支配人性的原則言，支配本我的是唯樂原則。例如嬰兒每感饑餓時即要求立刻喂奶，決不考慮母親有無困難。

自我（ego）

是個體出生后，在現實環(huán)境中由本我中分化發(fā)展而產生，由本我而來的各種需求，如不能在現實中立即獲得滿足，他就必須遷就現實的限制，并學習到如何在現實中獲得需求的滿足。從支配人性的原則看，支配自我的是現實原則。此外，自我介于本我與超我之間，對本我的沖動與超我的管制具有緩沖與調節(jié)的功能。

超我（superego）

是人格結構中居于管制地位的最高部分，是由于個體在生活中，接受社會文化道德規(guī)范的教養(yǎng)而逐漸形成的。超我有兩個重要部分：一為自我理想，是要求自己行為符合自己理想的標準；二為良心，是規(guī)定自己行為免于犯錯的限制。因此，超我是人格結構中的道德部分，從支配人性的原則看，支配超我的是完美原則。

人格結構中的三個層次相互交織，形成一個有機的整體。它們各行其責，分別代表著人格的某一方面：本我反映人的生物本能，按快樂原則行事，是“原始的人”；自我尋求在環(huán)境條件允許的條件下讓本能沖動能夠得到滿足，是人格的執(zhí)行者，按現實原則行事，是“現實的人”；超我追求完美，代表了人的社會性，是“道德的人”。

在通常情況下，本我、自我和超我是處于協調和平衡狀態(tài)的，從而保證了人格的正常發(fā)展。如果三者失調乃至破壞，就會產生心理障礙，危及人格的發(fā)展。