壓縮感知重構算法在稀疏信號恢復中的應用

宋曉霞，李 勇

（山西大同大學數學與計算機科學學院，山西 大同 037009）

壓縮感知重構算法在稀疏信號恢復中的應用

宋曉霞，李 勇

（山西大同大學數學與計算機科學學院，山西 大同 037009）

闡述了壓縮感知理論產生的背景、基本原理和應用方式,研究了兩類壓縮感知重構算法的重構思想和方法,并將兩類重構算法的典型算法正交匹配追蹤和基追蹤應用于稀疏信號的重構。結果表明：對于無噪觀測和含較小噪聲的觀測，正交匹配追蹤算法從重構頻率和重構時間兩方面顯示出更好的性能。

壓縮感知；重構算法；稀疏信號；貪婪追蹤算法；凸松弛算法

由于Shannon/Nyquist采樣定理能為模擬數據采樣提供理論基礎，因此它的提出是電子信息技術發展史上的一個重要里程碑事件。近半個世紀以來的數據采樣均以Shannon/Nyquist采樣定理為基礎。然而，在諸如圖像和視頻處理、超寬帶信號處理、核磁共振、空間探測、無線傳感器網絡等實際應用中，均需要兩倍帶寬的Nyquist采樣率，但硬件設備的升級還是無法滿足這些應用的需要。2006年D.Donoho、E.Candes和T.Tao等提出了一種被稱為壓縮感知（compressed sensing,CS）的新的信息獲取理論[1-2]。由于CS框架下的數據處理體系能利用稀疏信號的本質特征，用低維投影來捕捉高維信號的特征，并通過重構算法從低維投影中提取出高維信號的信息，因此，在它問世的短短幾年里就受到國內外學者的廣泛關注和研究。

1 CS理論

CS理論是集采樣與壓縮為一體的信息獲取理論。該理論[1-2]指出：在觀測矩陣滿足有限等距屬性（restricted isometry property,RIP）的條件下，解碼端能利用優化算法從O（k log（N/k））次觀測以很高的概率來完全地恢復信號，其中N是信號的長度，k是該信號的稀疏度。具體原理[3-4]為：假設一個長度為N的信號X是稀疏的或可壓縮的，并令Ψ表示其正交基或緊框架，如果將X的各分量投影到與變換基Ψ不相關的維數為M×N（M=N）的觀測矩陣Φ上，則可得觀測集合y∶M×1。那么信號X可以憑借這些觀測y通過求解優化問題（1）而精確恢復。

令Θ=ΦΨT，如果對于任意一個稀疏度為k的信號X和常數δk∈（0，1），矩陣Θ滿足式（2）,

則稱Θ滿足RIP屬性。當Θ滿足RIP屬性或觀測矩陣Φ和稀疏基Ψ不相關的條件下，CS能利用優化算法從少量的觀測數據中以很高的概率完全地重構出原始信號。CS的應用可以總結為：首先在采樣端對稀疏信號或可壓縮信號以遠低于Nyquist標準的采樣頻率進行信號采樣的同時，對數據進行了一定程度的壓縮，并進行存儲，傳輸到終端用戶后，在終端用戶通過優化重建的方法從壓縮觀測中提取原始信號的信息。因此，重構算法和觀測矩陣的構造是CS的兩個基本問題。本文主要關注壓縮感知的重構算法及其在稀疏信號恢復中的應用。

2 壓縮感知重構算法

CS中的信號重構問題可以建模成一個最小化l0范數問題。然而，該最小化問題的求解屬于NP難問題，需要找到信號分量中非零元素的所有組合，目前的方法均無法直接求解。為了逼近該問題的解，研究者們提出了系列求解的重構算法。它們基本可以歸結為貪婪迭代匹配追蹤算法和基于最小l1范數的凸松弛算法兩大類[5]。

2.1 貪婪追蹤算法

貪婪追蹤算法（greedy pursuit，GP）的基本思想是：在每次迭代時，確定產生最大信號改進質量的一個或更多分量來選擇一個局部最優解來逐步逼近原始信號。最早的貪婪追蹤算法可追溯到1993年Mallat與Zhang提出的匹配追蹤（matching pursuit，MP）算法[6]。該算法的思想可描述如下：在每一次迭代的過程中，先通過內積來計算相關性，再從過完備原子庫里挑選出與信號匹配的最佳原子，并計算殘差。然后繼續挑選與殘差最為匹配的原子，迭代重復上面的過程，信號最終可由選擇出的原子線性表示。然而，由于MP算法在每一次迭代中只能夠保證殘差信號與當前選擇的原子相互正交，而不能保證殘差信號同當前原子與先前選擇的原子所張成的子空間相互正交，因而降低了收斂速度。

為了獲得更好的收斂效果，Tropp and Gilbert等提出了更有效的正交匹配追蹤（orthogonalmatching pursuit,OMP）算法[7]。該算法采用了和MP算法相似的原子選擇準則。不同的是，OMP算法要先對所選擇的原子進行施密特正交化處理，然后將信號投影到那些正交原子構成的空間上，獲得信號在各個已選出原子上的分量和余量，再繼續對余量進行分解。由于每一步分解均要滿足內積最大的條件，因此，余量將會隨著分解步數的增加而迅速減小。

由于OMP算法的每一次迭代僅從原子庫中選擇一個原子，這使得殘差信號能量的衰減速度較慢。另外，該算法依據給定的最大迭代次數來終止迭代的過程使得它需要更多的觀測來保證信號的完全重構。為了加速殘差信號能量的衰減速度和減少信號重構所需要的觀測數據量，研究者們又給出了如下一系列追蹤算法。

（1）分段正交匹配追蹤（stagwise orthogonal matching pursuit，StOMP）算法。該算法每次匹配追蹤時選出多個匹配原子而不是單個原子，減少了總的匹配次數。在每一次迭代中，選擇所有與殘差內積系數幅度大于給定閾值的原子，然后計算當前殘差信號與所有選擇原子的最小二乘逼近，將逼近誤差作為新的殘差繼續迭代直到滿足停機條件為止。StOMP算法將OMP算法進行一定程度的簡化，提高了計算速度，但是由于其在每次迭代的過程中尋找的不一定是信號的最佳表示，降低了稀疏分解的精度，因此其分解速度是以逼近精度為代價的。

（2）正則正交匹配追蹤（regularized orthogonal matching pursuit，ROMP）算法[8]。與StOMP算法相似的是，ROMP算法每次匹配追蹤時也選出多個匹配原子而不是單個原子。與StOMP算法不同的是，ROMP算法不用閾值而用一個和目標向量相似的點積向量來選擇原子。在ROMP算法中，先依據相關性進行原子的一次篩選，再求觀測矩陣中各原子和余量之間的內積絕對值，并計算相關系數，依此將相關系數大的原子選入候選集合以便進行原子的二次篩選。然后采用正則化過程對原子進行二次篩選，將能量最大的一組相關系數對應的原子索引值加入支撐集。對未進入支撐集的那些原子，正則化過程可以保證它們的能量一定遠小于被選入原子的能量。由此可見它是一種簡單有效的原子篩選方法。ROMP算法是第一種有RIP界支撐的貪婪技術，它根據相關性增加了正則化后的二次篩選易獲得更精確的解。但是，它需要估測信號的稀疏度。若信號的稀疏度估計過小將會導致多次迭代也無法達到迭代終止條件；若信號的稀疏度估計過大將導致不理想的重構效果。因此，信號稀疏度的估計是ROMP算法的關鍵問題。

（3）壓縮采樣匹配追蹤（compressive sampling matching pursuit,CoSaMP）算法。該算法是一種引入回溯思想的壓縮采樣匹配追蹤算法，它融入了組合算法的思想來保證速度并提供了嚴格的錯誤界。CoSaMP算法不僅從原子庫中選擇多個較相關的原子，而且從候選集中剔除多個原子，因而可以提高算法的效率。該算法引入了回溯思想，重構質量與線性規劃算法相當，而且重構復雜度低，提供了更全面的理論保證。但是，它也是以估測信號稀疏度為前提的。對于稀疏度估測困難的

情況，可借用其它自適應的算法來實現。

2.2 凸松弛算法

除了貪婪追蹤算法之外，CS的另一類重構算法是在一定條件下將求解式（3）的l0優化問題松弛為求解式（4）的l1凸優化問題。

由于l0模型的求解屬于非凸問題的求解，而l1模型是與l0模型最接近的凸函數，因此很自然采用這種放松方式。并且一些文獻已經證明當觀測矩陣滿足RIP屬性時，l1模型的解與l0模型的解是等價的。

當觀測被噪聲污染的時候，可以通過求解下面的一些優化問題來重構信號。其中式（5）描述的模型為帶有不等式約束的BP模型。該模型需要知道噪聲的功率限，而對于實際情況，噪聲的功率限通常是未知的。式（6）描述的模型為另一類替代的凸優化方法，常稱為Dantzig Selector模型，當觀測足夠時，可通過求解該模型重構原始信號。然而，該優化方法需要噪聲和稀疏度的先驗知識。式（7）描述的模型為無約束的l1優化問題[9]，常稱為BPDN模型，它通過放松重構誤差幅度的硬約束為模型中軟權值λ。式（8）描述的模型為LASSO模型[10]。當λ從0取到無窮的時候，BPDN模型的解等價于當q從無限到0時LASSO模型的解。上面的這些優化算法均基于相同的原理：在觀測向量和稀疏基已知的條件下，用l1最小化來恢復稀疏逼近的非零系數的支撐集。通常在優化算法之后可以用去偏處理來減少重構誤差。

3 兩類算法在稀疏信號重構中的應用

該部分以稀疏信號作為測試信號，分別用兩類重構算法從無噪和含噪兩類壓縮觀測中提取信號。

3.1 無噪壓縮觀測

首先采用一個N=200，k=10的稀疏信號作為測試信號。對于M為3 k到7 k，間隔為k的高斯觀測分別獨立運行100次，采用OMP的貪婪匹配追蹤算法和BP的凸松弛算法進行信號重構，重構結果如表1所示。在無噪情況下，重構誤差小于1e-10，可以認為信號被重構。

從表1的數據能看出：OMP的貪婪匹配追蹤算法更適合于從無噪觀測中恢復稀疏信號。實際上，在上面的實驗中，BP算法并不是不能重構信號，而是重構的精度達不到1e-10，僅能達到1e-4。

3.2 含噪壓縮觀測

假設對上面的信號進行高斯觀測后，又被均值為0，標準差為0.01的高斯噪聲污染，采用OMP的貪婪匹配追蹤算法和BP的凸松弛算法進行信號重構，重構結果如表2所示。在此種含噪情況下，重構誤差小于0.02，認為信號被重構。

從表2的數據能看出：OMP的貪婪匹配追蹤算法更適合于小噪聲的壓縮觀測。對于噪聲較大的壓縮觀測，需要事先估測重構誤差，再進行實驗驗證，將在后續的工作中繼續研究和探討。

4 結束語

本文介紹了壓縮感知理論產生的背景，基本原理和應用方式。對壓縮感知重構算法的重要問題，進行了分析和總結。最后，將兩類重構算法的代表性算法OMP和BP應用于稀疏信號的重構。結果表明：對于無噪觀測和含較小噪聲的觀測，OMP算法從重構頻率和重構時間兩方面顯示出更好的性能。對于觀測噪聲較大的情況，需要通過估測噪聲后進行深入研究。

表1 OMP和BP算法從無噪觀測中恢復信號的重構結果

表2 OMP和BP算法從含噪觀測中恢復信號的重構結果

[1]Donoho D.Compressed sensing[J].IEEE Transaction.on Information Theory,2006,52（4）：1289-1306.

[2]Candes E,Wakin M.An introduction to compressive sampling[J].IEEE Signal Processing Magazine,2008,25（2）：21-30.

[3]石光明,劉丹華,高大化,等.壓縮感知理論及其研究進展[J].電子學報,2009,37（5）：1070-1081.

[4]宋曉霞，石光明.低冗余的壓縮感知觀測[J].西安電子科技大學學報，2012,39（4）：144-148.

[5]Tropp J，Wright S.Computationalmethods for sparse solution of linear inverse problems[J].Proceedings of the IEEE,2010,98（6）：948-958.

[6]Mallat S，Zhang Z.Matching pursuits with time-frequency dictionaries[J].IEEE Transaction on Signal Processing,1993,41（12）：3397-3415.

[7]Tropp J，Gilbert A.Signal recovery from random measurements via orthogonalmatching pursuit[J].IEEE Transaction on Information Theory,2007,53（12）：4655-4666.

[8]Needell D,Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J]. Foundations of ComputationalMathematics,2009,9（3）：317-334.

[9]Chen S,Donoho D,Saunders M.Atomic decomposition by basis pursuit[J].SIAMJournal on Scientific Computing,1999,20（1）：33 -61.

[10]TibshiraniR.Regression shrinkage and selection via the lasso[J].Journalof the Royal Statistical Society,1996,58（1）：267-288.

Abstract:To improve the security and success rate of transaction in B2C E-commerce and reflect the credibility of customer objectively,a trust evaluation mechanism is proposed base on cloud model theory.It aims to analyze the factors which affect online perception trust in B2C E-commerce from historical transaction evaluation,site popularity,commodity price,Logistics and services. By creating definition of the trust cloud,the qualitative description and quantitative representation of trust is unified.A new trust evaluationmodel is established based on algorithm of converse trust cloud generator and trustmerging and algorithm of similarity.At last,by the result of calculation combining with subjective inference decision-making of trust is realized.The results of simulation experiments show that the trustevaluationmodel is valid and rational.

Key words:B2C E-commerce；trust evaluation；cloud model；trust cloud

〔責任編輯 高 海〕

App lication of Sparse Signal Restoration via Reconstruction Algorithm s of Compressed Sensing

SONG Xiao-xia,LIYong
（School ofMathematics and Computer Science,ShanxiDatong University,Datong Shanxi,037009）

This paper illustrates the background,the basic principle and application of compressed sensing theory.Two kinds of reconstruction algorithms are studied from the idea and method.And then typical algorithms including orthogonalmatching pursuit and basis pursuit are applied to the reconstruction of sparse signals.The results suggest that orthogonalmatching pursuit algorithm shows better performances from the two aspects of reconstruction frequency and time for compressivemeasurements without noise or with small noise.

compressed sensing；reconstruction algorithm；sparse signal；greedy pursuit algorithm；convex relaxation algorithm

〔責任編輯 高 ?！?/p>

（School ofMathematics and Computer Science,ShanxiDatong University,Datong Shanxi,037009）

TN911

A

2013-08-01

國家自然科學基金資助項目[61307121]

宋曉霞（1975-），女，山西廣靈人，博士，副教授,研究方向：壓縮感知與無線傳感器網絡。

1674－0874（2013）05－0004－06