李昕藝，劉三陽，謝維，

（西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，陜西西安710126）

壓 縮 感 知 理 論（compressivesensing）由DONOHO等于2006年提出，可以從低維壓縮信號中高概率恢復(fù)原始高維信號［1-2］。應(yīng)用壓縮感知理論可降低信號的采樣和傳輸成本，是一種非常適合信息爆炸時代的信號采樣和處理理論。

壓縮感知理論包括信號的稀疏表示、觀測信號采集、信號重構(gòu)三部分。觀測信號采集是壓縮感知理論降低信號采集率的關(guān)鍵步驟，通過觀測矩陣的線性變換將高維信號投影為低維信號，公式為

其中，y∈ RM×1為觀測信號，x∈ RN×1為原始信號。由于M?N，該過程能顯著降低信號維數(shù)，為信號的存儲、傳輸提供便利。如何構(gòu)造有效的測量矩陣是觀測信號是否包含原信號全部信息的關(guān)鍵。

自壓縮感知理論問世以來，測量矩陣主要可分為隨機測量矩陣和確定性測量矩陣兩大類。隨機測量矩陣主要包括高斯隨機矩陣［3］、伯努利隨機矩陣［4］、部分傅里葉矩陣［5］等。這些矩陣均能在一定概率上重構(gòu)原始信號，但因隨機數(shù)的生成和存儲對硬件要求較高，往往難以實現(xiàn)。

由于隨機性測量矩陣在實際應(yīng)用中存在難以克服的缺點，確定性測量矩陣在壓縮感知理論中的應(yīng)用尤為重要。從構(gòu)造原理出發(fā)，確定性測量矩陣可分為4類：（1）基于有限域的測量矩陣［6］。從特定有效域出發(fā)，構(gòu)造滿足限制等容性［2］的測量矩陣；（2）基于編碼的測量矩陣［7］。針對特定的編碼構(gòu)造滿足指定性質(zhì)的測量矩陣；（3）基于訓(xùn)練的測量矩陣［8-9］。將隨機矩陣作為初始矩陣，結(jié)合稀疏基，不斷優(yōu)化，使得感知矩陣逼近ETF［10］框架的測量矩陣；（4）最大 Welch界等式測量矩陣［11］。利用數(shù)值搜索方向構(gòu)造最大Welch界等式測量矩陣。

本文基于共軛梯度法的感知矩陣優(yōu)化方法不同于常用的優(yōu)化測量矩陣方法，屬于確定性測量矩陣中的第3類構(gòu)造方法。在EFT框架的基礎(chǔ)上，通過優(yōu)化感知矩陣，并利用共軛梯度法生成下降方向，可實現(xiàn)加速下降，簡化梯度計算。仿真實驗表明，本方法在理論分析、實際圖像應(yīng)用及算法有效性方面均優(yōu)于其他方法。

1 預(yù)備知識

1.1 壓縮感知理論

由壓縮感知理論，信號y可稀疏表示為

其中，y∈RM×1為觀測信號；Φ∈RM×N為投影矩陣；Ψ∈RN×L為稀疏基；α∈RL×1為稀疏信號。這里D=ΦΨ為感知矩陣，需滿足限制等容性要求［2］。由于M?N，可實現(xiàn)信號壓縮與采樣同時進行，大幅度減少采樣量，從而減小數(shù)據(jù)的傳輸壓力。

信號x可應(yīng)用于壓縮感知理論的前提是該信號能被稀疏表示，即

若‖α ‖0=k(k ?N)，則稱 α 為k-稀疏信號，x為可k-稀疏化的。

將壓縮感知理論應(yīng)用于實際，需從觀測信號y中重構(gòu)原始信號，稱之為信號的重構(gòu)過程。該過程的原始模型為

由于該模型為非凸的欠定方程求解模型，有研究表明其等價于凸模型［12］：

由于l1范數(shù)是凸的，這樣就將一個非凸優(yōu)化問題轉(zhuǎn)化為凸優(yōu)化問題，方便求解。

1.2 觀測矩陣構(gòu)造

從測量信號y中重構(gòu)出精確唯一的原始信號x的［13］必要條件為感知矩陣D= ΦΨ ∈ RM×L滿足[13]：

其中，spark(D)為D中線性相關(guān)的列的最小數(shù)目；K為x的稀疏度。顯然spark(D)越大，對信號稀疏度的要求越低，信號重構(gòu)效果越好，但直接求解關(guān)于spark(D )的最大化問題十分困難。由文獻［13］知，當時，x也能被完美重構(gòu)，μ()D為D的相互關(guān)系數(shù)，定義為

其中{di}為D的列。文獻［14］給出了D的相互關(guān)系數(shù)的界限：

基于此，可利用D的Gram矩陣G=DTD來設(shè)計目標函數(shù)，其展開式為

G的非對角元素越接近0越好，故要求G接近對角矩陣，當然其非對角元素不可能為0。對G做歸一化處理 ，將其對角元素化為 1，即=ˉ，其中=DxDx，D=diag(… ,,… )。此時，顯然有對 ?i，有‖=1,則2的相互關(guān)系數(shù)為

文獻［10］首次提出用ETF框架來解決觀測矩陣的構(gòu)造問題，該框架要求歸一化的Gram矩陣Gˉ接近一個目標對角矩陣Gt，其中Gt從δeft中選擇：

常數(shù)ξ＞0，可限制搜索空間以找到合適的目標矩陣。

利用感知矩陣D的Gram矩陣在ETF框架下迭代產(chǎn)生感知矩陣來構(gòu)造測量矩陣。目標函數(shù)為

考慮到ETF框架需要對D進行歸一化處理，文獻［15］提出了利用μˉ)測量矩陣的構(gòu)造方法：

2 感知矩陣優(yōu)化方法

在文獻［15］的基礎(chǔ)上，引入共軛梯度來簡化梯度計算，同時觀察到在稀疏基Ψ已確定的情況下，觀測矩陣構(gòu)造過程和稀疏信號恢復(fù)過程中，用到的都是感知矩陣D而非觀測矩陣Φ。因此，本文設(shè)計了基于感知矩陣D的梯度的共軛梯度求解算法。模型為

由于該模型有2個變量D和Gt，因此，采用交替更新的方法分別求解。在固定Gt的情況下，采用共軛梯度法更新感知矩陣D；接著固定D，利用收縮算子更新目標Gram矩陣Gt。

2.1 共軛梯度法更新感知矩陣

記E=Gt-，則感知矩陣優(yōu)化模型可改寫為

對D求導(dǎo)，有

其中dij是D中第( )i,j個元素，又有

又

其中εmn為E的第(m,n)個元素，注意到=1，則上式可改寫為

整理得

文獻［15］中的梯度計算公式為

其中，Γ為對角矩陣，其對角元素與Q的對角元素相同，

與其相比，本文所設(shè)計的目標函數(shù)關(guān)于D的導(dǎo)函數(shù)少了一個矩陣乘法運算，更為簡單。

同時，為減少迭代次數(shù)，采用共軛梯度方法進行更新，直至得到最優(yōu)的感知矩陣D：

其中，λ為步長，V(k)為搜索方向。步長λk為序列{δj,j=1,2,… }中使函數(shù)值下降的最大值，其中δ ∈(0 ,1 )［16］。搜索方向 V(k)的更新方式如下：

其中因子βk的計算方法由文獻［17］給出：

2.2 收縮算子更新目標矩陣

用文獻［10］的方法來更新目標Gram矩陣Gt：

其中，ζ=G(k-1)(i , j)，ξ為ETF框架中限制搜索空間的參數(shù)。

固定稀疏基Ψ，給定初始測量矩陣Φ0，可得初始感知矩陣D0=ΨΦ0。本文所設(shè)計的基于共軛梯度法的感知矩陣D的優(yōu)化方法如下：

Algorithm 1感知矩陣優(yōu)化方法

輸入初始感知矩陣D0，初始下降方向d0，參數(shù)δ=0.5，迭代步數(shù)ite；

輸出最優(yōu)感知矩陣Dopt；

步驟1更新目標Gram矩陣Gtk；

步驟2計算歸一化感知矩陣Dˉk=DkDxk，并計算 Gˉk=DˉTDˉ；

步驟3計算梯度，計算因子 βk；

步驟4更新方向：βkV(k-1)a；

步驟5更新步長：選擇λk為序列{δj，j=1，2，…}中使得目標函數(shù)值下降的最大值。

步驟6更新感知矩陣：Dk=Dk-1+λV(k)；

步驟7若k＞ ite，則停止，輸出Dopt=Dk；否則，置k=k+1，轉(zhuǎn)步驟 1。

3 實驗結(jié)果

將 ELAD［18］、XU［19］、TIAN［20］及最新的 NSMD方法做對比，從理論分析、真實圖片恢復(fù)效果和算法效率三方面通過實驗驗證所提出的感知矩陣構(gòu)造方法的有效性。實驗環(huán)境為Matlab R2015b。

3.1 理論結(jié)果

由ETF框架可知，優(yōu)化后的感知矩陣D的Gram矩陣應(yīng)逼近一個對角矩陣。用D的相互關(guān)系數(shù)μ及平均相互關(guān)系數(shù)μav作為評價指標來衡量其Gram矩陣與對角矩陣的相似程度。計算方法如下［18］：

為方便比較，固定稀疏基為離散余弦變換基（DCT基），以上方法都為優(yōu)化同一個高斯隨機測量矩陣，且 固 定 迭 代 步 數(shù) 為 100，M=102，N=256，ξ=

圖1為未優(yōu)化的高斯隨機感知矩陣和ELAD、XU、TIAN、NSMD及本文方法構(gòu)造的感知矩陣的Gram矩陣非對角元素值的分布直方圖。非對角元素越小，所優(yōu)化的感知矩陣越好。由圖1可知，XU、ELAD和TIAN方法所得的非對角元素的值較大，且不接近0，NSMD及本文方法所得感知矩陣的非對角元素均較??；從平均值來看，本文方法略高于TIAN方法；但是從峰值來看，本文方法遠優(yōu)于ELAD、XU、TIAN方法，略優(yōu)于NSMD方法。表2顯示了各個方法的μ值和μav值。

3.2 實際圖像重構(gòu)效果

圖1 非對角元素值直方圖Fig.1 Histogram of the off-diagonal entries in the Grams

表1 算法性能比較Table 1 The comparison of algorithm performance

從圖1和表1中可以看出，本文方法顯著優(yōu)于XU、ELAD、TIAN方法，略優(yōu)于NSMD方法。為進一步觀測所構(gòu)造的感知矩陣在實際應(yīng)用中的優(yōu)勢，將各方法應(yīng)用于實際圖像（標準Lena圖，大小256×256）重構(gòu)中，觀察實驗效果。

實驗采用的字典矩陣由K-SVD算法［21］訓(xùn)練所得；重構(gòu)算法為OMP算法［22］，重構(gòu)過程的迭代步驟均為20。ELAD、XU、TIAN、NSMD及本文方法的迭代步數(shù)均為 100，M=102，N=256，δ=0.5，ξ=。重構(gòu)精度由PSNR衡量，由于對圖片進行了歸一化處理，PSNR計算公式為

為模擬現(xiàn)實情況中數(shù)據(jù)收集存在噪聲的特點，給圖片添加不同水平的高斯白噪聲，觀察各方法對噪聲的魯棒性，如圖2所示。

由圖2知，當高斯噪聲水平為10%時，所有方法均能較好重構(gòu)，其中ELAD和TIAN方法的效果較好。當添加方差為20%的高斯噪聲時，XU、ELAD、TIAN方法產(chǎn)生的重構(gòu)圖較為模糊，而NSMD和本文方法效果良好，且本文方法的PSNR值最高。當添加高斯噪聲水平為30%時，XU、ELAD、TIAN方法已不適用，而本文方法重構(gòu)效果依然良好，PSNR值較高。無論噪聲水平如何，在某些圖像塊中，本文方法得到的圖像較其他方法更為平滑。由此可知，本文方法對噪聲的魯棒性較高。

3.3 算法有效性

為觀察感知矩陣在不同稀疏度下對稀疏重構(gòu)的影響，利用人工生成的隨機信號來驗證本文算法對不同稀疏度信號的測量有效性。選擇在理論結(jié)果和真實圖片重構(gòu)實驗中表現(xiàn)較好的NSMD作為對比算法。重構(gòu)算法均為OMP算法，重構(gòu)精度由均方誤差（MSE）衡量，MSE越大，重構(gòu)精度越低。MSE計算公式為

圖2 圖像重構(gòu)圖Fig.2 Image recovery with different sensing matrix

圖3 顯示了固定N=80，M=15，信號稀疏度K從2到8變化時，MSE隨K變化的情況（結(jié)果為重復(fù)運行20次的平均值）。可以看出，隨著K值的增大，2種方法的重構(gòu)精度均逐漸降低，但本文方法的重構(gòu)精度要好于NSMD方法。

4 結(jié) 論

設(shè)計了一種基于ETF框架的新型感知矩陣構(gòu)造方法。感知矩陣由最小化其Gram矩陣和目標Gram矩陣之間的距離得到。由于求解感知矩陣的梯度比求解測量矩陣的梯度計算更簡單，且壓縮感知理論重構(gòu)原始信號中使用的是感知矩陣而非測量矩陣，本文設(shè)計了一種基于共軛梯度法的感知矩陣優(yōu)化算法：在迭代過程中交替更新目標Gram矩陣和感知矩陣，利用收縮算子更新目標Gram矩陣，利用共軛梯度算法更新感知矩陣，并且將感知矩陣的Gram矩陣歸一化過程封裝在算法內(nèi)部。該算法不同于常用的基于測量矩形梯度的求解算法。試驗結(jié)果表明，本文算法在理論分析、實際圖像應(yīng)用及算法有效性方面均具優(yōu)勢。

圖3 MSE隨稀疏度變化圖Fig.3 Mean square error versus signal sparsity