基于變換域的壓縮感知快速重構算法

唐川雁 史姣姣

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

關鍵詞：壓縮感知;頻域分析;稀疏信號;傳感矩陣;實變換;重構算法

DOI：10. 11907/rjdk. 182596 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：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-），女，杭州電子科技大學通信工程學院碩士研究生，研究方向為信號處理;史姣姣（1992-），女，杭州電子科技大學通信工程學院碩士研究生，研究方向為無線電軟件。

0 引言

壓縮感知（Compressed Sensing，CS）理論[1-3]自2006年誕生以來發展迅猛，已應用在圖像處理[4]、視頻編碼[5]、信道估計與信道編碼[6-7]、目標跟蹤[8-9]、模式識別[10]等諸多領域?；诮浀淠慰固夭蓸佣ɡ韀11]提出的壓縮感知理論，以低于奈奎斯特采樣定理要求的頻率對信號進行采樣，并在采樣的同時實現數據壓縮。但是該理論的前提是信號在時域必須是稀疏的，或經過某種變換在其它變換域是稀疏的，如離散小波變換、離散余弦變換、離散傅里葉變換等。在此條件下，利用測量矩陣對信號進行降維處理后得到測量矢量，再選擇恰當的重構算法即可從測量值中恢復原信號[12]。在這個過程中，測量矩陣與稀疏基相乘后可得傳感矩陣，而后續信號重構正是由傳感矩陣與測量矢量在迭代過程中匹配最佳原子來逼近原信號以求得稀疏解，再將其與變換基相乘得到最終的恢復信號，因此傳感矩陣和稀疏信號影響信號重構的復雜度。該過程求解是一個復雜的組合問題，很難找到滿足要求的最優解，一般都是求解其次優解。目前已有許多重構算法可以保證求出次優解，如梯度投影（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]等。最為經典的OMP算法在余量更新階段采用Schmidt正交化處理方法使當前原子與已選原子均正交，避免了原子的重復選擇，因此OMP算法的收斂過程更快，信號重建效果更好。然而OMP算法在每次迭代過程中都要進行Schmidt正交化處理，使運算量加大，且在迭代過程中每次只選擇一個原子，對于大規模問題花費時間較長。而IHT算法較為簡單、易于實現，在實際中應用較多，但其易受測量矩陣限制，計算復雜度高、運算時間長。

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

1 壓縮感知理論

設在[RN]空間中存在一個長度為[N]的離散信號[x]，可看作是一個[N×1]維的列向量?，F假設有一組基函數[ψ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]個非零值或重要元素，則可認為該信號在變換基上是稀疏的，稀疏度為[K]。CS通過矩陣[A∈RM×N]對信號[x（x∈RN）]進行觀測實現降維處理，其中[K

[y=Ax=Dα] （2）

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

從測量矢量[y]中重構出原始信號[x]的過程叫作CS恢復過程，即求解式（2）。因為[D]不是一個方陣[（M

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

2 基于CS復域到實域的快速重構算法

2.1 算法原理

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

圖1 本文算法模型

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

[xf=Fx] （4）

[x=F-1xf] （5）

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

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

然后利用本文算法獲得實矩陣[Dreal]和實矢量[xfreal]以降低復雜度，此時測量矢量[y]變為：

[y=Drealxfreal] （7）

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

2.2 數學分析

下面證明從復域到實域的轉換可得到同樣的觀測向量[y]，證明過程如下：

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

假設矩陣[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列的實部，[θmn]為矩陣[D]第m行n列的虛部。

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

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

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

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

3 仿真與分析

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

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

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

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

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

[ANMSE=15001500x-x22x22] （15）

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

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

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

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

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

4 結語

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

參考文獻：

[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] 金堅， 谷源濤， 梅順良. 壓縮采樣技術及其應用[J]. 電子與信息學報， 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]. 南京：南京郵電大學， 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] 程中建， 李康， 谷懿，等. 基于稀疏表達特征選擇的壓縮感知目標跟蹤算法[J]. 軟件導刊， 2018（7）：91-96.

[9] 黃慶俊， 何儒漢. 基于協方差矩陣的壓縮感知跟蹤算法[J]. 軟件導刊， 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] 王世一. 數字信號處理 [M].修訂版.北京：北京理工大學出版社， 2006.

[12] 倪加明， 孫欽者， 陸家明. 一種改進的稀疏度自適應壓縮采樣匹配追蹤算法[J]. 通信技術， 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.

（責任編輯：杜能鋼）