李 曙，毛承敏，楊 喜，尹 里，梁 俊

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

?

基于子空間追蹤的稀疏信號重構(gòu)算法

李 曙，毛承敏，楊 喜，尹 里，梁 俊

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

信號重構(gòu)算法是壓縮感知理論中的重要環(huán)節(jié)，其優(yōu)劣影響壓縮感知的重構(gòu)效果.基于子空間追蹤算法，對經(jīng)稀疏表示和測量矩陣壓縮后的信號進行重構(gòu)驗證，理論分析和實驗結(jié)果表明，子空間追蹤算法能使信號在較高壓縮比下保持良好的重構(gòu)效果.

子空間追蹤；稀疏信號；信號重構(gòu)；Nyquist采樣

Nyquist采樣定理指出，只有當(dāng)信號采樣頻率高于或等于信號帶寬的2倍時，采樣得到的數(shù)字信號才能精確恢復(fù)原始信號.然而，隨著現(xiàn)代通信和信號處理技術(shù)向更高頻、更大數(shù)據(jù)量方向發(fā)展，如超寬帶通信、太赫茲技術(shù)等，對信號的帶寬要求越來越大，由此引發(fā)的采樣頻率、通信速率、存儲空間的需求也越來越高.為了能以更低的成本和更高的效率滿足這種需求，近年來人們致力于研究以遠低于Nyquist采樣頻率對信號采樣并恢復(fù)原始數(shù)據(jù)的技術(shù).

1 壓縮感知原理

圖1 壓縮感知示意

許多自然信號在時域上并不是稀疏信號，但在某個變換域上卻是稀疏的.利用傅里葉變換、短時傅里葉變換、小波變換和Gabor變換等稀疏變換工具，將原始信號轉(zhuǎn)換為變換域中的稀疏信號，這類信號稱為可壓縮信號[1].對于稀疏的或是可壓縮的信號，可采用一種與Nyquist不同的采樣理論,這就是Donoho D L等[2]于2006年提出的壓縮感知理論.該理論證明了用遠低于Nyquist采樣頻率對原始信號采樣，得到的低維信號可以近乎完美地重構(gòu)原始信號.信號壓縮感知過程如圖1所示.

圖1中虛線所示部分為虛擬部分，在實際中不執(zhí)行.令實際信號x∈Rn在某個變換域是稀疏的，變換矩陣為Ψ∈Rn×n，則x=Ψα.其中系數(shù)向量α∈Rn，是x的K稀疏表示.信號x經(jīng)Ψ變換后變?yōu)橄∈栊盘?，再?jīng)感知矩陣Φ∈Rm×n(m?n)壓縮便得到輸出信號

y=ΦΨα.

(1)

由于壓縮感知的輸出信號y∈Rm(m?n)，因此(1)式是一欠定的矩陣方程，無法得到該矩陣方程的解析解.當(dāng)感知矩陣Φ滿足約束等距條件

(2)

其中δK是一個與稀疏度K有關(guān)的常數(shù)，且0≤δK<1.

求解(1)式欠定矩陣方程的方法有多種，其基本思想是通過稀疏向量的支撐區(qū)的識別，將欠定的稀疏矩陣方程變換為超定的矩陣方程.常見算法包括基追蹤(BP)[3]、正交匹配追蹤(OMP)[4]、迭代硬閾值(IHT)[5]、子空間追蹤(SP)[6]、梯度追蹤[7]等.

2 子空間追蹤算法

子空間追蹤算法是稀疏信號重構(gòu)算法的一種，與常規(guī)的匹配追蹤類算法的原子選擇機制類似.其不同之處在于子空間追蹤算法引入了“回退機制”.對于K稀疏的信號，每次迭代過程中其標簽集的候選列個數(shù)均為K，且其候選列在迭代過程中是動態(tài)更新的.正交匹配追蹤算法在每次迭代過程中，其標簽集中候選列的個數(shù)加1，且候選列一旦加入標簽集將不會退出.因此，子空間追蹤算法比匹配追蹤類算法有更高的重建效率和更好的重建質(zhì)量.其具體執(zhí)行過程如下：

Input 稀疏度 K，感知矩陣,觀測向量.

Initialize (1)Ω0={向量ΦTy中具有最大幅值的K個元素的標簽集合}；

Iteration 對k=1,2,…,執(zhí)行以下運算.

Step 3 Ωk={向量xp中具有最大幅值的K個標簽集合}.

Step 5 若‖rk‖2>‖rk-1‖2,則令Ωk=Ωk-1，并退出迭代；否則令k=k-1,并返回Step 1,繼續(xù)新一輪迭代.

3 稀疏信號重構(gòu)實驗

為驗證信號重構(gòu)的有效性，筆者利用子空間追蹤(SP)算法分別對一維稀疏信號和二維圖像信號進行重構(gòu)實驗.實驗數(shù)據(jù)來源長度為256、稀疏度為30的高斯隨機信號，測量矩陣為高斯隨機矩陣.實驗結(jié)果如圖2所示.由圖2可知，子空間追蹤算法幾乎完美地重構(gòu)了原始信號，重構(gòu)誤差極小(在10-16數(shù)量級).

圖2 一維稀疏信號重構(gòu)實驗結(jié)果

為更全面地衡量算法的有效性，將重構(gòu)實驗重復(fù)執(zhí)行1 000次，在不同稀疏度下，運行時間及重構(gòu)成功的概率如表1所示.隨著稀疏度K的增大，重構(gòu)耗時隨之增大，重構(gòu)成功率隨之下降.稀疏度小于40時能準確重構(gòu)，大于50時則重構(gòu)成功率急劇下降.實驗所用計算機配置為:intel至強雙核CPU，主頻3 GHz，內(nèi)存為4 G，系統(tǒng)為Windows 8,實驗軟件為Matlab 2012b.

現(xiàn)以256×256的lena灰度圖像作為二維圖像信號實驗對象，以隨機高斯矩陣作為采樣矩陣.先對原始圖像進行小波變換，將其變換到小波域(二維圖像信號在小波域中為稀疏信號).在采樣長度M與圖像長度N的比值α分別為0.3,0.4,0.5,0.6,0.7的情況下，利用子空間追蹤方法重構(gòu)的二維圖像如圖3所示.

表1 不同稀疏度下的重構(gòu)耗時和成功率

圖3 不同壓縮比的二維圖像信號重構(gòu)結(jié)果比較

從圖3的重構(gòu)結(jié)果可知，在壓縮比較小時，圖像重構(gòu)質(zhì)量較差，隨著壓縮比增大，圖像的重構(gòu)效果越來越好.在壓縮比α=0.5時已有較好的重構(gòu)質(zhì)量.同時，圖像重構(gòu)耗時也隨壓縮比的增加而增加.在不同壓縮比的重構(gòu)圖像峰值信噪比(PSNR)及重構(gòu)耗時如表2所示.

表2 不同壓縮比的重構(gòu)圖像的PSNR值和耗時

4 結(jié)語

用子空間追蹤算法對一維稀疏隨機信號和二維圖像信號進行重構(gòu)驗證，實驗結(jié)果證明，當(dāng)信號的稀疏度較小時，子空間追蹤算法可以近乎完美地重構(gòu)原始信號.算法的運算時間隨著稀疏度的增大而增加，但重構(gòu)效果隨之變差.在實際應(yīng)用中，某些場合的測量矩陣可能不滿足約束等距性條件，其稀疏信號重構(gòu)問題將是下一步的研究方向.

[1] 張賢達.矩陣分析與應(yīng)用[M].第2版.北京：清華大學(xué)出版社，2013:82-84.

[2] DONOHO D L.Compressed Sensing[J].IEEE Transaction Information Theory,2006,52:1 289-1 306.

[3] CHEN S S,DONOHO D,SAUNDERS M.Atomic Decomposition by Basis Pursuit[J].SIAM Review，1998，43(1)：129-159.

[4] PATI Y C,REZAIIFAR R，KRISHNAPRASAD P S.Orthogonal Matching Pursuit:Recursive Function Approximation with Applications to Wavelet Decomposition[C]∥Proceeding 27th Asilomar Conference on Signals,Systems and Computers,1993：40-44.

[5] BLUMENSATH T,DAVIES M E.Iterative Thresholding for Sparse Approximations[J].The Journal of Fourier Analysis and Applications，2008，14：1-28.

[6] DAI W,MILENKOVIC O.Subspace Pursuit for Compressive Sensing Signal Reconstruction[J].IEEE Transaction on Information Theory，2009，55(5)：2 230-2 249.

[7] BLUMENSATH T,DAVIES M E.Gradient Pursuits[J].IEEE Transmation on Signal Processing,2008,56(6):2 370-2 382.

(責(zé)任編輯 陳炳權(quán))

Sparse Signal Reconstruction Algorithm Based on Subspace Pursuit

LI Shu,MAO Chengmin,YANG Xi,YIN Li,LIANG Jun

(School of Information Science and Engineering,Jishou University,Jishou 416000,Hunan China)

Signal reconstruction algorithm plays an important part in the theory of compressive sensing and determines the reconstruction quality of compressive sensing.In this paper,based on the subspace pursuit(SP) algorithm,the signal is reconstructed after sparse representation and compression by the measurement matrix.Theoretical analysis and experimental results show that subspace pursuit algorithm can maintain good effect of signal reconstruction at higher compression ratio.

subspace pursuit;sparse signal;signal reconstruction;Nyquist sampling

1007-2985(2015)04-0023-03

李 曙(1985—)，湖南南縣人，吉首大學(xué)信息科學(xué)與工程學(xué)院講師，電子科技大學(xué)博士生，主要從事信號與信息處理研究.

TN911

A

10.3969/j.issn.1007-2985.2015.04.006