王紅亮，盧振國，王 帥，曹京勝，呂云飛

(中北大學電子測試技術重點實驗室，山西 太原 030051)

基于稀疏度自適應算法的壓縮感知

王紅亮，盧振國，王 帥，曹京勝，呂云飛

(中北大學電子測試技術重點實驗室，山西太原030051)

針對目前壓縮感知的重構算法需預知信號稀疏度和重構時間較長的問題，提出基于稀疏度自適應算法的壓縮感知，該方法基于分段和回溯思想，通過增大步長、合并上次原子來選擇最匹配原子，能顯著減小計算復雜度，從而減少信號重構時間。以語音信號為處理對象，對SAMP算法進行了仿真比較，仿真結果表明，在未知信號稀疏度的情況下，與基追蹤(BP)算法和正交匹配追蹤(OMP)算法比較，SAMP算法的重構信號運行時間明顯降低，并且在不同的信號壓縮比的條件下重構信號性能得以保證，驗證了SAMP算法在稀疏度方面的自適應性以及重構效率高等優(yōu)點。

壓縮感知；稀疏度自適應算法；重構時間

0 引言

近年，Donoho、Candès、Romberg和Tao提出了新的信號壓縮采樣理論——壓縮感知[1-4](Compressive Sensing，CS)，以低于奈奎斯特采樣率的速度對信號進行采樣。CS主要內容是將稀疏信號通過觀測矩陣從高階矩陣線性投影為低階，最后高概率精確地重建原信號。這種新型的采樣方式避免了傳統(tǒng)香農采樣先采樣再丟棄的缺點，同時降低了采樣率，縮減了存儲數(shù)據(jù)，從而有效地減少了傳輸和存儲設備的使用量。所以壓縮感知提出后在光學成像[5]、雷達探測[6]和語音信號處理[7-9]等眾多領域都有相關的研究。

重建算法作為壓縮感知過程中的一個至關重要的環(huán)節(jié)，其主要目的是要實現(xiàn)從現(xiàn)有的低維數(shù)據(jù)中最大限度地恢復出原始的高維數(shù)據(jù)。重構算法的選擇應遵循使用較少的觀測值，并且能精確和快速地恢復原信號等原則。目前，重構算法有兩大類應用較為廣泛：松弛法[10-11]、貪婪算法[12-13]。松弛法中應用較廣泛的有基追蹤(Basic Pursuit，BP)算法，具有重構信號的質量較好，需要觀測的個數(shù)較少的特點，但計算復雜度較高，恢復信號時間較長，而貪婪算法中具有代表性的正交匹配追蹤(Orthogonal Matching Pursuit，OMP)算法需要將原始信號內的N個元素逐一恢復，而且每次重構時恢復數(shù)據(jù)的計算存在誤差，同時需要較多的觀測次數(shù)，重構信號的質量也相對較低。

壓縮感知理論可以將信號通過觀測矩陣從高階矩陣投影到低階，最后高概率恢復出原信號，解決了香農-奈奎斯特采樣定理在信號采集中的不足，同時還具有低采樣率和重構質量高等優(yōu)點。壓縮感知對信號是非自適應性采樣，只能將可稀疏的信號隨機觀測得到壓縮值，雖然壓縮不同類型語音信號或者圖像信號考慮了選取合適稀疏矩陣和重構算法，但僅僅針對某一類信號，而不是根據(jù)采樣信號本身的特征自適應的壓縮和重構，所以根據(jù)信號自身特征引入自適應稀疏算法是目前壓縮感知研究的難點和熱點。本文針對目前重構算法均存在需預先確定信號稀疏度，恢復時間較長等缺陷，采用稀疏自適應匹配追蹤算法(Sparse Adaptive Matching Pursuit，SAMP)[14]實現(xiàn)重構原始信號，與其他重構算法相比較，SAMP算法具有在未知稀疏度的情況下高概率的恢復原信號，同時重構信號的時間顯著減少等優(yōu)點。

1 壓縮感知理論

壓縮感知理論的主要過程：首先判斷信號本身或者在某個域是否稀疏(或可壓縮)，如果稀疏再通過觀測矩陣使信號從高階矩陣線性投影變?yōu)榈碗A，信號的采集和壓縮在此過程同時進行，最后通過恢復算法高概率精確地重建原始信號。壓縮感知的理論包含三個內容：選擇信號稀疏基，設計觀測矩陣和重構原信號。其中信號是否具有稀疏性是前提條件；觀測矩陣的設計是重要的組成部分，它的設計不僅關系到壓縮和采樣速率的快慢，而且影響重構信號的質量；重構原始信號是其核心部分，因此，重構算法是否合適決定恢復原信號質量的好壞。壓縮感知實現(xiàn)需要滿足一些條件：信號在某個變換域是可稀疏，稀疏矩陣和觀測矩陣盡量不相干，感知矩陣滿足RIP準則等。

根據(jù)以上條件可以建立如下算法數(shù)學模型：

假定有限實值離散空間為RN，其中Ψi(i=1,2,…,N)是RN的基向量，則長度為N的原始信號x可表示為：

(1)

式(1)中，Ψ=[Φ1,Φ2,…,ΦN]，Ψ是由基向量Φ1構成的N×N正交矩陣，矩陣s是信號x在Ψ域的稀疏后的矩陣。

然后采用與Ψ相干性較小的觀測矩陣Φ(M×N,M?N)對信號進行線性投影，得到觀測值y：

y=Φx

(2)

觀測值y是M階列矩陣，注意：在此過程中觀測值y不是原信號的采樣值，而是信號x在觀測矩陣Φ上的投影值。由于信號x是可稀疏矩陣，所以式(2)可以表示為：

y=Φx=ΦΨs=Θs

(3)

式(3)中，Θ(M×N矩陣)為感知矩陣。

從觀測值y準確地恢復原始信號x最直接的方法是轉化為L0范數(shù)的最優(yōu)化問題：

(4)

但直接求式的解是個NP-hard問題[15]。Donoho認為最優(yōu)化問題與信號稀疏分解兩者有共同點，所以最優(yōu)化問題的求解途徑可以從信號稀疏分解相關理論中尋找，證明最小L0范數(shù)下在一定條件下和最小L1范數(shù)具有等價性找到最稀疏的解。所以，式(4)可轉化為L1最小范數(shù)下的最優(yōu)化問題：

(5)

2 恢復算法

2.1 正交匹配追蹤法

OMP算法延續(xù)了匹配追蹤算法中原子的選擇準則，主要過程：從感知矩陣Θ中選擇與余量(觀測值的殘差)相乘的最大值的列矩陣，再利用最小二乘法得到最匹配的原子，循環(huán)直至逼近原信號，實現(xiàn)了遞歸地對已選原子集合進行正交化以保證迭代的最優(yōu)性，從而減少了迭代次數(shù)。

下面簡單敘述OMP算法：

輸入條件：感知矩陣Θ，觀測值y，稀疏度k；

輸出：x的k稀疏信號s的逼近sr，重構誤差r；

初始化：余量r0=y，重建信號s0=0，索引集Γn=Γn-1∪{k}，迭代次數(shù)n=0；

步驟1：計算余量和感知矩陣Θ的每一列的內積gn=ΘTrn-1；

步驟 2：找出gn中元素最大的元素

j=argmax|gn[i]|；

步驟 3：更新索引集Γn=Γn-1∪{j}及原子集合Θrn=Θrn-1{θj}；

步驟 4：使用最小二乘法求得近似解

步驟5：更新余量rn=y-Θsn；

步驟6：判斷是否滿足收斂條件，滿足則停止sr=sn，r=rn輸出sr，sn，否則轉步驟1。

OMP算法保證了每次迭代的最優(yōu)性，減少了迭代的次數(shù)，易于實現(xiàn)。但需要預先知道信號的稀疏度K才能進行重構，在每次迭代中僅選取一個原子來更新新原子集，并且迭代的次數(shù)與稀疏度K和采樣個數(shù)M密切相關，隨著迭代次數(shù)的增大，這樣必然會造成重構時間增大，并且重構時每次恢復都有微小誤差。

2.2 基于SAMP算法的壓縮感知

稀疏自適應匹配追蹤算法是基于OMP算法基礎上提出的，SAMP算法的主要思路是：在未知稀疏度K的情況下進行信號重構，利用逐步加大步長的方法不斷增加所用的原子規(guī)模，并引入回溯思想，在每次加大步長和選擇原子后，都會與上一步的原子進行合并，最后從中選擇最佳的匹配原子。與其它貪婪算法相比，SAMP算法中回溯思想引入，使得在稀疏度K未知的前提下能夠自適應重構原信號，顯著提高了算法精度并減少了信號恢復時間。

SAMP算法實現(xiàn)步驟如下：

輸入條件：觀測值y，觀測矩陣Φ，步長增量L；

初始化：余量r0=y，支撐集量F0=Φ,步長Γ=L,階段內初始迭代次數(shù)i=1，步長增量的初始倍數(shù)j=1；

步驟1：求解感知矩陣Θ和殘差余量內積p=|Φ·rn-1|,取絕對值最大的Γ個數(shù)據(jù)，將相應的感知矩陣Θ的列矩陣與候選集Wi合并；

步驟2：將支撐集Fi-1和候選集Wi合并，得到候選集Ci，

Ci=Fi-1∪Wi；

同時選擇最大的Γ個元素的列矩陣，合并成新支撐集F；

步驟4：通過觀測值y和支撐集F，計算余量r:

和OMP算法需預知稀疏度K不同，SAMP算法中階段思想和回溯思想的引入,通過階段與階段間的累加來不斷增大支撐集的大小，同時不斷更新支撐集，實現(xiàn)了在稀疏度K未知的前提下能夠自適應重構原信號的目的。SAMP算法通過將迭代過程分為多個階段，在每個階段中信號重建所需的支撐集的大小不發(fā)生改變，通過選取感知矩陣和余量的內積中最大的一些值形成候選集，在經過循環(huán)從候選集中選擇支撐集中的原子，所以初始步長的確定就成為該算法的重建時間和重建質量的關鍵因素。

在SAMP算法中，特定的步長有不同的恢復效果，若步長Γ=1時，支撐集的大小可以達到稀疏度的大小，但對于大規(guī)模信號，重建時間將會很長。若步長Γ過大時，重建時間將會減少，但支撐集的大小很有可能會超越K，導致重建效果變差。因此，重建信號需要在重建時間和效果中取得平衡，根據(jù)信號和壓縮比對步長進行合理的選擇。

3 實驗仿真及分析

本章節(jié)選用語音信號作為仿真對象，通過仿真證明SAMP算法與OMP、BP算法相比在信號恢復質量和信號重構時間上的優(yōu)勢。仿真實驗將SAMP算法引入壓縮感知，稀疏基選用冗余字典(K-SVD)算法，觀測矩陣則是以隨機高斯矩陣為基礎，根據(jù)每幀語音信號能量的大小，自適應分配觀測的個數(shù)，采用SAMP 算法重構恢復語音信號。

首先選用一段女生聲音內容為“hello，酷狗”，共有44 100個樣點，采樣率為22.05 kHz。為了說明SAMP算法的重建效果，三種重構算法對語音信號均采用相同的預處理方法，進而重構語音信號。SAMP采用初始步長Γ=10，迭代停止條件ε=0.000 2，幀長取160，240，320，400，480，信號壓縮比值取0.3，0.4，0.5，0.6。

3.1 信號評價方法

1)評價語音信號的客觀方法

衡量一段語音信號恢復質量，一般采用平均幀信噪比(AFSNR，Average Frame Signal to Noise Ratio)和相對誤差進行客觀評價，其中 AFSNR 越大則說明重構信號質量越好，反之，重構信號越差。定義如下：

(6)

式(6)中，N是語音信號的總幀數(shù)。

2)評價語音信號的主觀方法

MOS(Mean Opinion Score)值一般作為評價語音信號的主觀方法，本文采用 ITU P.862的 PESQ 程序對語音信號和重構信號的對比來得到 MOS值，實現(xiàn)主觀質量的客觀評價

3.2 仿真結果

三種算法重構信號的AFSNR和MOS值如表1和表2中所示。根據(jù)表中數(shù)據(jù)分析可知：語音信號的幀長和壓縮比值都對重構信號的AFSNR有影響，當幀長固定時，信號壓縮比值越大，重構信號的AFSNR越大，說明重構語音的質量越高；當信號壓縮比值不變時，語音的幀的樣點越多，重構信號的AFSNR越大，表示恢復語音信號的質量越好，當幀長為400，壓縮比值為0.6時，重構信號的質量達到最好。三種算法重構信號的質量性能相比較結果如圖1所，在相同幀長和壓縮比值的情況下，SAMP算法重構的語音質量稍好于BP算法，相對優(yōu)于OMP算法。

表1 OMP，BP和SAMP算法的平均幀重構信噪比

表2 OMP，BP和SAMP算法重構信號的MOS值

以重構語音時間的角度評判，運行觀測矩陣大概只需要1 s左右，剩余全部都是重構信號所用時間。從實驗數(shù)據(jù)中不難發(fā)現(xiàn)，SAMP算法的重構時間都在10 s以內，但OMP算法最少時間的是10 s，而隨著壓縮比的增大，重構語音所需要的時間成倍增加，最高達到400 s，BP算法的時間重構更長，最小的是40 s，最高2 500 s，這么長的時間恢復一段語音信號是難以想象的。如圖2所示，在相同幀長和信號壓縮比值的條件下，OMP算法的重構時間是SAMP算法的15倍左右，而BP算法是SAMP算法的幾百倍，所以使用SAMP算法會顯著減少壓縮感知重構語音信號的時間。

OMP算法雖然保證了每次迭代的最優(yōu)性，減少了迭代的次數(shù)，但缺點是：需要預先知道信號的稀疏度K才能進行重構，在恢復過程中將原信號N個元素逐一恢復從而使得觀測次數(shù)較多，并且重構時每次恢復都有微小誤差，重構信號的質量比BP算法要低，但BP算法優(yōu)化信號較為復雜，需要恢復信號的時間較長。SAMP算法與OMP算法有所不同，每次都選擇原子更新原信號重構所需要的支撐集，并且利用回溯思想將所選原子和上次的支撐集進行合并，從而得到候選集，最后篩選出新的支撐集，SAMP是在自適應的基礎上引入回溯思想，使它的恢復精度高于OMP算法。

4 結論

本文提出了基于稀疏度自適應算法的壓縮感知，該方法在未知稀疏度K的情況下進行信號重構，基于分段和回溯思想，通過增大步長、合并上次原子來選擇最匹配原子，能顯著減小計算復雜度，從而減少信號重構時間。仿真結果表明，在未知信號稀疏度的情況下，與基追蹤(BP)算法和正交匹配追蹤(OMP)算法比較，SAMP算法的重構信號運行時間明顯降低，并且在不同的信號壓縮比的條件下重構信號性能得以保證， 驗證了SAMP算法在稀疏度方面的自適應性以及重構效率高等優(yōu)點。

[1]David L Donoho. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4):1289-1306.

[2]E Candès, M Wakin. An introduction to compressive sampling[J]. IEEE Signal Processing Magazine,2008,25(2):21-30

[3]Donoho David L, Tsaig Y. Extensions of compressed sensing[J]. Signal Processing, 2006,86(3):533-548.

[4]Candès E, Romberg J, Tao Terence. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006,52(2):489-509.

[5]Lustig M, Donoho D, Pauly J M. Sparse MRI: The application of compressed sensing for rapid MR imaging[J]. Magnetic Resonance in Medicine, 2007, 58(6): 1182-1195.

[6]Duarte M F, Davenport M A, Takhar D, et al. Single-pixel imaging via compressive sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2): 83-91.

[7]Michal A, Elad M, Alfred B. K-SVD: An algorithm for designing over-complete dictionaries for sparse representation[J]. IEEE Transactions on Signal Processing, 2006, 54(11):4311-4322.

[8]周小星,王安娜,孫紅英,等.基于壓縮感知過程的語音增強[J]. 清華大學學報(自然科學版),2011,51(9):1234-1238.

[9]Griffin A, Hirvonen T, Tzagkarakis C, et al. Single-channel and Multi-channel sinusoidal audio coding using compressed sensing[J]. IEEE Transactions on Audio Speech and Language Processing, 2011,19(5):1382 - 1395.

[10]Donoho David. For most large underdetermined systems of linear equations, the minimal ell-1 norm solution is also the sparsest solution[J]. Communications on Pure and Applied Mathematics, 2006,59(6): 797-829.

[11]Malioutov D M, Cetin M, Willsky A S. Homotopy continuation for sparse signal representation[C]//IEEE International Conference on Acoustics, Speech, and Signal Processing.Philadelphia, USA: IEEE Press,2005:733-736.

[12]Needell D, Vershynin R. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J]. Foundations of Comp. Math,2000,9(3):317-334.

[13]Needell D, Tropp J. Cosamp: Iterative signal recovery from incomplete and inaccurate samples [J]. Applied and Comput. Harmon. Anal. 2009,26(3):301-321.

[14]焦李成,楊淑媛,劉芳,等.壓縮感知回顧與展望[J].電子學報，2011,39(7):1651-1662.

[15]Thong T Do, Lu Gan, Nam Nguyen, et al. Sparsity adaptive matching pursuit algorithm for practical compressed sensing [C]//Asilomar Conference on Signals, Systems and Computers. Pacific Grove, California, 2008.

AdaptiveAlgorithmforSparsityCompressiveSensing

WANG Hongliang, LU Zhenguo, WANG Shuai, CAO Jingsheng, Lü Yunfei

(Key Laboratory of Instrumentation Science & Dynamic Measurement North University of China, Taiyuan 030051, China)

The current compressive sensing needs signal sparsity in advance and the reconstruct process sustained over long time.To solve the problem, a sparsity adaptive algorithm(SAMP) was put forward in this paper.The method was based on segmentation and retrospective thinking. By increasing step and merging last atom to select the best match, this algorithm could significantly reduce the computational complexity, thereby reduced the time signal reconstruction. The speech signal was processed in comparison with SAMP algorithm simulation. Simulation results showed that, in the case of unknown signals sparsity, the reconstructed signal quality of SAMP algorithm reduced the reconstruction time evidently comparing with the base pursuit(BP) algorithm and the orthogonal matching pursuit(OMP) algorithm. At the same time, the reconstructed signal quality of SAMP had a good performance under different signal compression ratio.

compressive sensing; sparsity adaptive algorithm; reconstruction time

2017-04-25

王紅亮(1978—)，男，河南林州人，副教授，研究方向：測試系統(tǒng)集成，目標檢測與識別，應用軟件開發(fā)，超聲成像。E-mail:nucwanghongliang@163.com。

TP391.41

A

1008-1194(2017)05-0040-05