基于變換域的壓縮感知快速重構(gòu)算法

唐川雁 史姣姣

摘 要：壓縮感知是信號處理領(lǐng)域熱門研究課題，其應(yīng)用前提為原信號是稀疏或可壓縮的。時(shí)域非稀疏信號可以變換為頻域稀疏信號，但變換后的信號和傳感矩陣表示形式為復(fù)數(shù)，增加了重構(gòu)復(fù)雜度。為了降低復(fù)雜度，提高信號重構(gòu)效率，提出一種基于實(shí)變換的重構(gòu)算法，該算法將復(fù)數(shù)形式的稀疏信號和傳感矩陣的實(shí)部和虛部分離后再參與重構(gòu)。與傳統(tǒng)重構(gòu)算法相比，該算法改善了重構(gòu)信號的均方誤差，明顯縮短了重構(gòu)時(shí)間，極大提高了信號重構(gòu)效率。

關(guān)鍵詞：壓縮感知;頻域分析;稀疏信號;傳感矩陣;實(shí)變換;重構(gòu)算法

DOI：10. 11907/rjdk. 182596 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號：TP312文獻(xiàn)標(biāo)識(shí)碼：A 文章編號：1672-7800（2019）007-0096-04

Fast Reconstruction Algorithm Based on Transformation Domain

for Compressed Sensing

TANG Chuan-yan，SHI Jiao-jiao

（School of Communication Engineering，Hangzhou Dianzi University，Hangzhou 310018，China）

Abstract： Compressed Sensing is a hot research theory in the field of signal processing in recent years.Its application precondition is that the original signal is sparse or compressible.Time domain non-sparse signals can be transformed into frequency domain sparse signals，but the transformed signal and sensor matrix are expressed in the complex number? increasing the complexity of reconstruction.In order to reduce complexity and improve the efficiency of signal reconstruction， a reconstruction algorithm based on real transformation is proposed.The algorithm separates the real and imaginary parts of complex sparse signal and sensor matrix，then participating in the reconstruction operation.Experiments show that compared with the traditional reconstruction algorithms， the proposed algorithm improves the mean square error of reconstructed signal，shortens the reconstruction time and greatly improves the efficiency of signal reconstruction.

Key Words： compressed sensing;frequency domain analysis;sparse signal;sensor matrix;real transformation; reconstruction algorithm

作者簡介：唐川雁（1993-），女，杭州電子科技大學(xué)通信工程學(xué)院碩士研究生，研究方向?yàn)樾盘柼幚?史姣姣（1992-），女，杭州電子科技大學(xué)通信工程學(xué)院碩士研究生，研究方向?yàn)闊o線電軟件。

0 引言

壓縮感知（Compressed Sensing，CS）理論[1-3]自2006年誕生以來發(fā)展迅猛，已應(yīng)用在圖像處理[4]、視頻編碼[5]、信道估計(jì)與信道編碼[6-7]、目標(biāo)跟蹤[8-9]、模式識(shí)別[10]等諸多領(lǐng)域?；诮?jīng)典奈奎斯特采樣定理[11]提出的壓縮感知理論，以低于奈奎斯特采樣定理要求的頻率對信號進(jìn)行采樣，并在采樣的同時(shí)實(shí)現(xiàn)數(shù)據(jù)壓縮。但是該理論的前提是信號在時(shí)域必須是稀疏的，或經(jīng)過某種變換在其它變換域是稀疏的，如離散小波變換、離散余弦變換、離散傅里葉變換等。在此條件下，利用測量矩陣對信號進(jìn)行降維處理后得到測量矢量，再選擇恰當(dāng)?shù)闹貥?gòu)算法即可從測量值中恢復(fù)原信號[12]。在這個(gè)過程中，測量矩陣與稀疏基相乘后可得傳感矩陣，而后續(xù)信號重構(gòu)正是由傳感矩陣與測量矢量在迭代過程中匹配最佳原子來逼近原信號以求得稀疏解，再將其與變換基相乘得到最終的恢復(fù)信號，因此傳感矩陣和稀疏信號影響信號重構(gòu)的復(fù)雜度。該過程求解是一個(gè)復(fù)雜的組合問題，很難找到滿足要求的最優(yōu)解，一般都是求解其次優(yōu)解。目前已有許多重構(gòu)算法可以保證求出次優(yōu)解，如梯度投影（Gradient Projection For Sparse Reconstruction，GPSR）算法[13]、迭代硬閾值（Iterative Hard Thresholding，IHT）算法[14]、正交匹配追蹤（Orthogonal Matching Pursuit，OMP）算法[15-16]、壓縮采樣匹配追蹤（Compressive Sampling MP，CoSaMP）算法[17]、正則化正交匹配追蹤（Regularized Orthogonal Matching Pursuit，ROMP）算法[18]、分段式正交匹配追蹤（Stagewise OMP，StOMP）算法[19]等。最為經(jīng)典的OMP算法在余量更新階段采用Schmidt正交化處理方法使當(dāng)前原子與已選原子均正交，避免了原子的重復(fù)選擇，因此OMP算法的收斂過程更快，信號重建效果更好。然而OMP算法在每次迭代過程中都要進(jìn)行Schmidt正交化處理，使運(yùn)算量加大，且在迭代過程中每次只選擇一個(gè)原子，對于大規(guī)模問題花費(fèi)時(shí)間較長。而IHT算法較為簡單、易于實(shí)現(xiàn)，在實(shí)際中應(yīng)用較多，但其易受測量矩陣限制，計(jì)算復(fù)雜度高、運(yùn)算時(shí)間長。

為克服上述算法的不足，學(xué)者Nouasria & Et-Tolba[20]通過傳感矩陣乘以逆稀疏矩陣改善重建信號性能，而本文旨在降低時(shí)域非稀疏信號轉(zhuǎn)換為頻域稀疏信號后以復(fù)數(shù)形式增加的重構(gòu)復(fù)雜度，將得到的頻域稀疏信號和復(fù)數(shù)傳感矩陣以實(shí)數(shù)形式表現(xiàn)，從而在一定程度上減少誤差及算法運(yùn)算時(shí)間，加快算法收斂速度。

1 壓縮感知理論

設(shè)在[RN]空間中存在一個(gè)長度為[N]的離散信號[x]，可看作是一個(gè)[N×1]維的列向量。現(xiàn)假設(shè)有一組基函數(shù)[ψi（i=1，2，？，N）]也是[N×1]維的，若[x]可用[ψi]的線性組合表示，令[Ψ=[ψ1，ψ2，？，ψN]]，則[x]可表示為：

[x=Ψα=i=1Nψiαi] （1）

式（1）中，[Ψ]為稀疏基（變換基），[α=[α1，α2，？，αN]T]稱為稀疏矢量。若矢量[α]只存在至多[K]個(gè)非零值或重要元素，則可認(rèn)為該信號在變換基上是稀疏的，稀疏度為[K]。CS通過矩陣[A∈RM×N]對信號[x（x∈RN）]進(jìn)行觀測實(shí)現(xiàn)降維處理，其中[K

[y=Ax=Dα] （2）

式（2）中，[D=A×Ψ∈RM×N]為傳感矩陣，[A]為測量矩陣。

從測量矢量[y]中重構(gòu)出原始信號[x]的過程叫作CS恢復(fù)過程，即求解式（2）。因?yàn)閇D]不是一個(gè)方陣[（M

通過相關(guān)重構(gòu)算法，如OMP算法、IHT算法，就可利用已知的觀測向量[y]和傳感矩陣[D]求得稀疏表示向量[α]，進(jìn)而求出信號[x]。

2 基于CS復(fù)域到實(shí)域的快速重構(gòu)算法

2.1 算法原理

在信號重建過程中，測量矩陣與稀疏基相乘后可得傳感矩陣，而后續(xù)信號重構(gòu)正是由傳感矩陣與測量矢量在迭代過程中匹配最佳原子來逼近原信號以求得稀疏解，再將其與變換基相乘得到最終的恢復(fù)信號，因此傳感矩陣和稀疏信號影響信號重構(gòu)的復(fù)雜度。本文所提算法的系統(tǒng)框圖如圖1所示，在恢復(fù)過程之前分離傳感矩陣和經(jīng)過稀疏變換的信號虛部，變成實(shí)矩陣和實(shí)信號以降低算法復(fù)雜度。

圖1 本文算法模型

設(shè)長度為[N]的輸入信號[x]為時(shí)域非稀疏信號，通過傅里葉變換為頻域稀疏信號[xf]：

[xf=Fx] （4）

[x=F-1xf] （5）

再通過測量矩陣[A]獲得測量值[y]：

[y=Ax=AF-1xf=Dxf] （6）

然后利用本文算法獲得實(shí)矩陣[Dreal]和實(shí)矢量[xfreal]以降低復(fù)雜度，此時(shí)測量矢量[y]變?yōu)椋?/p>

[y=Drealxfreal] （7）

由已知的測量矢量[y]和實(shí)傳感矩陣[Dreal]，再利用某種重構(gòu)算法即可獲得稀疏解[xf]，然后通過逆傅里葉變換獲得恢復(fù)的原信號[x]。經(jīng)過此算法后，稀疏信號和傳感矩陣由原來的復(fù)數(shù)形式變?yōu)閷?shí)數(shù)形式。而在數(shù)據(jù)處理中，處理實(shí)數(shù)比復(fù)數(shù)更加簡單且出錯(cuò)概率小，因此由傳感矩陣與測量矢量在迭代過程中匹配最佳原子來逼近原信號求得的稀疏解，其均方誤差更小，算法收斂速度更快，減少了重構(gòu)運(yùn)行時(shí)間。

2.2 數(shù)學(xué)分析

下面證明從復(fù)域到實(shí)域的轉(zhuǎn)換可得到同樣的觀測向量[y]，證明過程如下：

信號恢復(fù)過程依賴[D]和[xf]的復(fù)雜度，因此，將[D]和[xf]由復(fù)域變成實(shí)域可改善信號恢復(fù)性能。

假設(shè)矩陣[D]為[m×n]維，[xf]為[n×1]維，則[m×1]維的觀測向量[y]為：

[D=A×F-1=ψ11+jθ11? ？？？？? ？？？ψ1n+jθ1n? ? ? ？？？？? ? ? ? ?？？？？？? ? ?？？？？？？？？？？？？？？？？ψm1+jθm1? ？? ψmn+jθmn] （8）

其中[F-1]為逆傅里葉變換矩陣，[ψmn]為矩陣[D]第m行n列的實(shí)部，[θmn]為矩陣[D]第m行n列的虛部。

[xf=（R1+jI1，？，Rn+jIn）T] （9）

[Rn]為稀疏信號[xf]第n行的實(shí)部，[In]為稀疏信號[xf]第n行的虛部。得到[D]和[xf]后，由兩者相乘便能得到測量矢量[y]，如下所示：

接下來分離[m×n]維復(fù)矩陣[D]的實(shí)部和虛部得到維度為[m×2n]的實(shí)矩陣[Dreal]，分離[n×1]維稀疏信號[xf]的實(shí)部和虛部得到維度為[2n×1]維的實(shí)稀疏信號[xfreal]：

由以上分析可知，式（10）和式（13）得到同樣的觀測向量[y]，表明由復(fù)域到實(shí)域的變換在數(shù)學(xué)上證明是正確的，并且這種變換在一定程度上降低了誤差，這是由于處理實(shí)矩陣比復(fù)矩陣容易得多，重構(gòu)時(shí)間更短。

3 仿真與分析

本文使用長度為[n=1024]的正弦信號作為輸入信號：

[x=0.6sin2π29nt-1.5sin2π100nt+sin2π200nt+]

[0.8sin2π400nt+2sin2π500nt-sin2π600nt] （14）

選擇測量矩陣[A]為高斯隨機(jī)矩陣，將時(shí)域非稀疏信號[x]變換為頻域稀疏信號[xf]，稀疏度為12，測量向量[y=Ax=AF-1xf]，維度為[m×1]，仿真時(shí)取[m=roundλ n]，其中[λ=mn]稱為壓縮率;變換復(fù)矩陣[D=AF-1]為實(shí)矩陣[Dreal=[real（D） -imag（D）]]，維度為[m×2n]。變換復(fù)向量[xf]為實(shí)向量，[xfreal=[real（xf）? imag（xf）]T]維度為[2n×1]，此時(shí)測量向量[y=Drealxfreal];用其中一種重構(gòu)算法重構(gòu)信號，如IHT算法，得到恢復(fù)的稀疏信號[xf=xf（1：n）+ixf（n+1：2n）]，再通過逆傅里葉變換得到估計(jì)的正弦信號[x]。

計(jì)算平均歸一化均方誤差（Average Normalized Mean Square Error，ANMSE），表達(dá)式為：

[ANMSE=15001500x-x22x22] （15）

為了驗(yàn)證本文算法的有效性，選擇高斯隨機(jī)矩陣作為測量矩陣。重構(gòu)算法以IHT算法、OMP算法為例，取[m=λn]，其中[λ]稱為壓縮率且[λ=0.1：0.1：0.9]，分別驗(yàn)證算法的重構(gòu)時(shí)間、平均歸一化均方誤差隨壓縮率的變化情況。固定測量值[m=256]，取[k=τm]，其中[k]為標(biāo)準(zhǔn)測量稀疏度且[τ=0.1：0.1：0.9]，驗(yàn)證重構(gòu)時(shí)間、平均歸一化均方誤差隨[τ]的變化情況，每種情況均運(yùn)行程序500次求平均值。仿真環(huán)境為Win10 64位系統(tǒng)Intel奔騰G4560處理器的Matlab2014a，結(jié)果如圖2、圖3所示。

圖2 本文算法與IHT算法比較

圖3 本文算法與OMP算法比較

由圖2（a）可知，隨著[λ]值的增大，在重構(gòu)時(shí)間上本文算法比IHT算法優(yōu)勢明顯，最大可縮短時(shí)間72.59%，是IHT算法所用時(shí)間的27.40%。隨著[λ]的增大，優(yōu)勢漸不明顯，但所用時(shí)間總是比IHT算法少。圖2（b）中，[τ]較小時(shí)本文算法較IHT算法優(yōu)勢不大。但隨著[τ]的增大，IHT算法在重構(gòu)時(shí)間上增長很快，而本文算法增長較為緩慢。當(dāng)[τ=0.9]時(shí)，本文算法所用時(shí)間比IHT算法少了75.72%。

圖2（c）中，本文算法開始與IHT算法相比均方誤差相當(dāng)，當(dāng)[λ0.7]時(shí)小于IHT算法。而圖2（d）中，兩種算法均方誤差均隨著[τ]的變化而變化，但本文算法誤差更小。圖3（a）、圖3（b）中，本文算法與OMP算法相比，本文算法的重構(gòu)時(shí)間始終小于OMP算法，最大時(shí)間分別減少44.69%和60.82%;圖3（c）、圖3（d）中，與OMP算法相比，本文算法在重構(gòu)誤差上改善明顯。綜上所述，本文算法在保證重構(gòu)誤差與原算法相當(dāng)甚至更小的基礎(chǔ)上，極大程度地減少了重構(gòu)時(shí)間，算法收斂速度更快，信號重構(gòu)效率更高。

4 結(jié)語

時(shí)域非稀疏信號轉(zhuǎn)換為頻域稀疏時(shí)，使用傅里葉變換將導(dǎo)致稀疏信號和傳感矩陣為復(fù)數(shù)形式而增加信號重構(gòu)復(fù)雜度和運(yùn)行時(shí)間。本文提出一種由復(fù)域到實(shí)域的變換方法改善算法性能，通過分離稀疏信號與傳感矩陣的實(shí)部和虛部降低復(fù)雜度，加快算法收斂速度，提高重構(gòu)效率。與傳統(tǒng)算法相比，所提算法在改善均方誤差的情況下極大程度減少了重構(gòu)運(yùn)行時(shí)間，算法收斂速度更快，信號重構(gòu)效率更高。鑒于本文的變換域只是傅里葉基且只對兩種算法進(jìn)行了比較，其它算法與本文算法的性能比較結(jié)果還有待進(jìn)一步驗(yàn)證。因此，將來要與更多算法進(jìn)行比較驗(yàn)證，以增加本文算法的普適性和魯棒性。

參考文獻(xiàn)：

[1] DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory， 2006， 52（4）：1289-1306.

[2] CANDèS E J. Compressive sampling[J]. Marta Sanz Solé， 2006， 17（2）：1433-1452.

[3] 金堅(jiān)， 谷源濤， 梅順良. 壓縮采樣技術(shù)及其應(yīng)用[J]. 電子與信息學(xué)報(bào)， 2010， 32（2）：470-475.

[4] LI Q，HAN Y，DANG J. Image decomposing for inpainting using compressed sensing in dct domain[M]. New York：Springer-Verlag Inc，2014.

[5] 顧瑩. 基于壓縮感知的分布式視頻編解碼及其圖像超分辨率重建研究[D]. 南京：南京郵電大學(xué)， 2011.

[6] NIAZADEH R，GHALEHJEGH S H，BABAIE-ZADEH M，et al. Adaptive and non-adaptive isi sparse channel estimation based on slo and its application in ml sequence-by-sequence equalization[M]. Latent Variable Analysis and Signal Separation. Springer Berlin Heidelberg， 2010：579-587.

[7] CANDES E J， TAO T. Decoding by linear programming[J]. IEEE Transactions on Information Theory， 2005， 51（12）：4203-4215.

[8] 程中建， 李康， 谷懿，等. 基于稀疏表達(dá)特征選擇的壓縮感知目標(biāo)跟蹤算法[J]. 軟件導(dǎo)刊， 2018（7）：91-96.

[9] 黃慶俊， 何儒漢. 基于協(xié)方差矩陣的壓縮感知跟蹤算法[J]. 軟件導(dǎo)刊， 2017， 16（4）：31-34.

[10] WRIGHT J， YANG AY， GANESH A， et al. Robust face recognition via sparse representation.[J]. IEEE Trans Pattern Anal Mach Intell， 2009， 31（2）：210-227.

[11] 王世一. 數(shù)字信號處理 [M].修訂版.北京：北京理工大學(xué)出版社， 2006.

[12] 倪加明， 孫欽者， 陸家明. 一種改進(jìn)的稀疏度自適應(yīng)壓縮采樣匹配追蹤算法[J]. 通信技術(shù)， 2016， 49（8）：992-996.

[13] FIGUEIREDO M A T， NOWAK R D， WRIGHT S J. Gradient projection for sparse reconstruction： application to compressed sensing and other inverse problems[C]. IEEE Journal of Selected Topics in Signal Processing， IEEE Journal of Selected Topics in Signal Processing， 2007：586 - 597.

[14] BLUMENSATH T， DAVIES M E. Iterative hard thresholding for compressed sensing[J]. Applied & Computational Harmonic Analysis， 2009， 27（3）：265-274.

[15] TROPP J A， GILBERT A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory， 2007， 53（12）：4655-4666.

[16] PATI Y C， REZAIIFAR R， KRISHNAPRASAD P S. Orthogonal matching pursuit： recursive function approximation with applications to wavelet decomposition[C]. Signals， Systems and Computers， 1993 Conference Record of The Twenty-Seventh Asilomar Conference on. IEEE， 2002：40-44 .

[17] NEEDELL D， TROPP J A. Cosamp： iterative signal recovery from incomplete and inaccurate samples [J]. Applied & Computational Harmonic Analysis， 2008， 26（3）：301-321.

[18] NEEDELL D， VERSHYNIN R. Uniform uncertainty principle and signal recovery via？regularized orthogonal matching pursuit[J]. Foundations of Computational Mathematics， 2009， 9（3）：317-334.

[19] DONOHO D L， TSAIG Y， DRORI I， et al. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J]. IEEE Transactions on Information Theory， 2012， 58（2）：1094-1121.

[20] NOUASRIA H，ET-TOLBA M. New sensing approach for compressive sensing using sparsity domain[C].2018 19th IEEE Mediterranean Electrotechnical Conference （MELECON）， Marrakech， 2018：20-24.

[21] CANDèS E J. The restricted isometry property and its implications for compressed sensing[J]. Comptes rendus - Mathématique， 2008， 346（9）：589-592.

（責(zé)任編輯：杜能鋼）