宋曉霞，李 勇

（山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西 大同 037009）

壓縮感知重構(gòu)算法在稀疏信號(hào)恢復(fù)中的應(yīng)用

宋曉霞，李 勇

（山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西 大同 037009）

闡述了壓縮感知理論產(chǎn)生的背景、基本原理和應(yīng)用方式,研究了兩類壓縮感知重構(gòu)算法的重構(gòu)思想和方法,并將兩類重構(gòu)算法的典型算法正交匹配追蹤和基追蹤應(yīng)用于稀疏信號(hào)的重構(gòu)。結(jié)果表明：對(duì)于無噪觀測(cè)和含較小噪聲的觀測(cè)，正交匹配追蹤算法從重構(gòu)頻率和重構(gòu)時(shí)間兩方面顯示出更好的性能。

壓縮感知；重構(gòu)算法；稀疏信號(hào)；貪婪追蹤算法；凸松弛算法

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

1 CS理論

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

令Θ=ΦΨT，如果對(duì)于任意一個(gè)稀疏度為k的信號(hào)X和常數(shù)δk∈（0，1），矩陣Θ滿足式（2）,

則稱Θ滿足RIP屬性。當(dāng)Θ滿足RIP屬性或觀測(cè)矩陣Φ和稀疏基Ψ不相關(guān)的條件下，CS能利用優(yōu)化算法從少量的觀測(cè)數(shù)據(jù)中以很高的概率完全地重構(gòu)出原始信號(hào)。CS的應(yīng)用可以總結(jié)為：首先在采樣端對(duì)稀疏信號(hào)或可壓縮信號(hào)以遠(yuǎn)低于Nyquist標(biāo)準(zhǔn)的采樣頻率進(jìn)行信號(hào)采樣的同時(shí)，對(duì)數(shù)據(jù)進(jìn)行了一定程度的壓縮，并進(jìn)行存儲(chǔ)，傳輸?shù)浇K端用戶后，在終端用戶通過優(yōu)化重建的方法從壓縮觀測(cè)中提取原始信號(hào)的信息。因此，重構(gòu)算法和觀測(cè)矩陣的構(gòu)造是CS的兩個(gè)基本問題。本文主要關(guān)注壓縮感知的重構(gòu)算法及其在稀疏信號(hào)恢復(fù)中的應(yīng)用。

2 壓縮感知重構(gòu)算法

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

2.1 貪婪追蹤算法

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

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

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

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

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

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

情況，可借用其它自適應(yīng)的算法來實(shí)現(xiàn)。

2.2 凸松弛算法

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

由于l0模型的求解屬于非凸問題的求解，而l1模型是與l0模型最接近的凸函數(shù)，因此很自然采用這種放松方式。并且一些文獻(xiàn)已經(jīng)證明當(dāng)觀測(cè)矩陣滿足RIP屬性時(shí)，l1模型的解與l0模型的解是等價(jià)的。

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

3 兩類算法在稀疏信號(hào)重構(gòu)中的應(yīng)用

該部分以稀疏信號(hào)作為測(cè)試信號(hào)，分別用兩類重構(gòu)算法從無噪和含噪兩類壓縮觀測(cè)中提取信號(hào)。

3.1 無噪壓縮觀測(cè)

首先采用一個(gè)N=200，k=10的稀疏信號(hào)作為測(cè)試信號(hào)。對(duì)于M為3 k到7 k，間隔為k的高斯觀測(cè)分別獨(dú)立運(yùn)行100次，采用OMP的貪婪匹配追蹤算法和BP的凸松弛算法進(jìn)行信號(hào)重構(gòu)，重構(gòu)結(jié)果如表1所示。在無噪情況下，重構(gòu)誤差小于1e-10，可以認(rèn)為信號(hào)被重構(gòu)。

從表1的數(shù)據(jù)能看出：OMP的貪婪匹配追蹤算法更適合于從無噪觀測(cè)中恢復(fù)稀疏信號(hào)。實(shí)際上，在上面的實(shí)驗(yàn)中，BP算法并不是不能重構(gòu)信號(hào)，而是重構(gòu)的精度達(dá)不到1e-10，僅能達(dá)到1e-4。

3.2 含噪壓縮觀測(cè)

假設(shè)對(duì)上面的信號(hào)進(jìn)行高斯觀測(cè)后，又被均值為0，標(biāo)準(zhǔn)差為0.01的高斯噪聲污染，采用OMP的貪婪匹配追蹤算法和BP的凸松弛算法進(jìn)行信號(hào)重構(gòu)，重構(gòu)結(jié)果如表2所示。在此種含噪情況下，重構(gòu)誤差小于0.02，認(rèn)為信號(hào)被重構(gòu)。

從表2的數(shù)據(jù)能看出：OMP的貪婪匹配追蹤算法更適合于小噪聲的壓縮觀測(cè)。對(duì)于噪聲較大的壓縮觀測(cè)，需要事先估測(cè)重構(gòu)誤差，再進(jìn)行實(shí)驗(yàn)驗(yàn)證，將在后續(xù)的工作中繼續(xù)研究和探討。

4 結(jié)束語

本文介紹了壓縮感知理論產(chǎn)生的背景，基本原理和應(yīng)用方式。對(duì)壓縮感知重構(gòu)算法的重要問題，進(jìn)行了分析和總結(jié)。最后，將兩類重構(gòu)算法的代表性算法OMP和BP應(yīng)用于稀疏信號(hào)的重構(gòu)。結(jié)果表明：對(duì)于無噪觀測(cè)和含較小噪聲的觀測(cè)，OMP算法從重構(gòu)頻率和重構(gòu)時(shí)間兩方面顯示出更好的性能。對(duì)于觀測(cè)噪聲較大的情況，需要通過估測(cè)噪聲后進(jìn)行深入研究。

表1 OMP和BP算法從無噪觀測(cè)中恢復(fù)信號(hào)的重構(gòu)結(jié)果

表2 OMP和BP算法從含噪觀測(cè)中恢復(fù)信號(hào)的重構(gòu)結(jié)果

[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ìn)展[J].電子學(xué)報(bào),2009,37（5）：1070-1081.

[4]宋曉霞，石光明.低冗余的壓縮感知觀測(cè)[J].西安電子科技大學(xué)學(xué)報(bào)，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

〔責(zé)任編輯 高 ?！?/p>

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

〔責(zé)任編輯 高 ?！?/p>

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

TN911

A

2013-08-01

國(guó)家自然科學(xué)基金資助項(xiàng)目[61307121]

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

1674－0874（2013）05－0004－06