一種基于PEG的構(gòu)造矩陣在壓縮感知中的應(yīng)用

杜鳳強，葉 潤，閆 斌

(電子科技大學 傳感網(wǎng)絡(luò)與智能信息處理實驗室，四川 成都，611731)

0 引言

隨著信息量的不斷增加，信號帶寬越來越寬，隨之而來的采樣速率也是越來越高，人們希望降低如此巨大的數(shù)據(jù)處理壓力。在實際應(yīng)用中，我們獲取的信息中大部分是不被利用的，并且這部分的數(shù)據(jù)對于整體數(shù)據(jù)并沒有太多的影響，那為何不直接去獲得我們需要的那部分數(shù)據(jù)呢？實際上，有損壓縮技術(shù)在數(shù)據(jù)處理方面的成果應(yīng)用從某種意義上驗證了人們的設(shè)想。作為一種全新信號采樣理論，壓縮感知打破了傳統(tǒng)奈奎斯特理論限制，在信號稀疏或可壓縮的基礎(chǔ)上，實現(xiàn)數(shù)據(jù)降維，并通過有效算法，從部分測量數(shù)據(jù)集中恢復出全局信息。理論一經(jīng)問世，便取得了廣泛關(guān)注，近幾年在多個領(lǐng)域取得了有效進展。本文基于信道編碼理論，對壓縮感知測量矩陣進行了淺顯的研究，驗證壓縮感知理論和低密度奇偶校驗碼間的理論聯(lián)系，并使用稀疏校驗矩陣設(shè)計原則構(gòu)造了壓縮感知測量矩陣。

1 壓縮感知

壓縮感知(Compressed Sensing，CS)是在信號采集的同時完成對信號的壓縮，理論本身是“通過對信號的高度不完備線性測量的高精確重建”。假設(shè)x(數(shù)字圖像或數(shù)字信號)是n空間中的一個未知向量，其在某個正交基(Wavelet，F(xiàn)ourier等)或緊框架(Curvelet，Gabor等)下有一個稀疏表示：x=Ψθ，其中‖θ‖0≤k，即x為k稀疏信號。對于這樣的n維信號x只需m=O(n1/4log5/2(n))個測量樣本，即可在特定的算法下準確恢復[1]。

令Φ∈m×n表示壓縮感知測量矩陣，令y表示包含m個測量值的實向量。最優(yōu)的壓縮感知過程是通過測量矩陣直接觀測出信號x(c∈n)的m個測量值，即求解問題：

CS1:min‖x‖0s.t.Φ·x=y，

(1)

這一問題可看作部分線性解碼問題[2]。

在CS1問題求解中，一方面，0范數(shù)的求解為NP-Hard問題；另一方面，如果一個問題可以被表示為凸優(yōu)化(Convex optimization)問題，就可以認定其一定可以得到很好的解決。對于凸優(yōu)化問題來說，局部最優(yōu)解就是全局的最優(yōu)解[3]，可以通過對部分測量信息的求解而得到滿足全局信息的解。在滿足一定約束的情況下，l0范數(shù)求解問題可轉(zhuǎn)化為l1范數(shù)下的凸優(yōu)化問題求解：

CS2:min‖x‖1s.t.Φ·x=y。

(2)

壓縮感知理論[4-5]證明了在適當?shù)臏y量矩陣Φ下最小l0范數(shù)優(yōu)化問題可轉(zhuǎn)化為求解最小l1范數(shù)優(yōu)化問題。在線性稀疏域中，一個“好”測量矩陣Φ∈m×n僅需m=O(klog(n/k))行就可實現(xiàn)k-稀疏信號的高概率重建。

(3)

(4)

此時，對于滿足式(4)中零空間特性的測量矩陣，認為問題CS2的求解等價于問題CS1的求解。這一結(jié)論在文獻[6]中以定理的形式給出。

2 LDPC碼與壓縮感知的聯(lián)系

信道編碼又稱差錯控制編碼，是一種通過對原始信號添加校驗冗余以抵抗錯誤干擾的技術(shù)[7]。在新一代移動通信中，低密度奇偶校驗( Low-density Parity-check，LDPC)碼[8]作為增強移動寬帶場景下數(shù)據(jù)信道編碼方案。線性是指碼字信息位與監(jiān)督位之間為線性關(guān)系，二者間滿足特定的線性方程組。分組是指在編碼過程中將待編碼信息進行分組，每組信息碼再附加若干監(jiān)督碼。分組碼用符號(n,k)表示，n表示碼長，k表示碼字中信息碼元的數(shù)目，re=n-k則為監(jiān)督位數(shù)目。分組碼的結(jié)構(gòu)為圖1所示。

圖1 分組碼結(jié)構(gòu)Fig.1 Structure of block code

低密度體現(xiàn)在校驗矩陣H為稀疏矩陣，即矩陣的行、列中非零元素數(shù)目(也稱行重、列重)非常小。奇偶校驗是奇校驗和偶校驗的總稱，規(guī)定了GF(2)中碼字中“1”的數(shù)目，二者原理相同。以偶校驗為例：偶校驗中，監(jiān)督位使得碼字中“1”的數(shù)目為偶數(shù)，即滿足：

an-1⊕an-2⊕…⊕a1⊕a0=0，

(5)

接收端若計算為“0”則認為無錯碼，奇校驗同理。

(6)

(7)

為了簡化計算及表述簡潔，常常將概率比轉(zhuǎn)化為對數(shù)形式。又因為平方誤差函數(shù)是線性的，且一個線性函數(shù)總在一個凸集(Convex Set)的極值點中獲得最小值，所以對問題CD1的求解又可寫作：

CD2:min〈λ,x′〉 s.t.x′∈conv(Ccc)。

(8)

問題CD2的求解復雜度是指數(shù)級的，F(xiàn)eldman[9-10]對以上問題的求解進行了轉(zhuǎn)化，對Ccc的凸包(Convex Hull)conv(Ccc)進行了擴展，轉(zhuǎn)而尋找問題的最優(yōu)解，降低了求解的復雜度。

(9)

則Hcc的基礎(chǔ)多胞形(Fundamental Polytope)定義為集合：

(10)

(11)

其中

(12)

證明：在矩陣Φ的基錐中，所有的向量ω∈n滿足

|ωi|≥0, ?i∈I(Φ)，

(13)

(14)

令ω?|v|，顯然有任意的ω滿足式(13)。當v∈Nullsp(Φ)，對于有即對于有由此，可以得出：

(15)

即任意的向量滿足式(14)，得證。

3 G-PEG測量矩陣

為驗證稀疏校驗矩陣可作為壓縮感知測量矩陣，本節(jié)基于校驗矩陣設(shè)計原則構(gòu)造壓縮感知測量矩陣，在現(xiàn)有漸進邊生長法基礎(chǔ)上提出分組漸進邊生成算法(Progressive Edge Growth by Group，G-PEG)，在賦予矩陣一定結(jié)構(gòu)規(guī)律的同時，保持了隨機特性。矩陣所有校驗節(jié)點的集合記為C，所有變量節(jié)點的集合記為V，實現(xiàn)步驟如下：

步驟3：分組結(jié)束條件判斷：若Vn的長度為0(n整除m)，結(jié)束分組；若Vn的長度小于m(n不能整除m)，將Vn中元素放入最后一個分組slast中，結(jié)束分組。

步驟4：確定分組s0連接到校驗節(jié)點c0。

步驟5：當sj連接ci時，若ci為sj-1的相連節(jié)點或者為sj-1相連節(jié)點的鄰節(jié)點，則索引i自增1，當不存在滿足條件的i時，sj連接c0。

其中，步驟1對輸入?yún)?shù)m和n進行參數(shù)計算；步驟2～3對校驗矩陣集合進行分組，獲得所有變量節(jié)點的隨機排列；步驟4～5生成邊，生成原則為相鄰的分組sj所連接的校驗節(jié)點ci不相同且不相鄰。

圖2 一維信號重構(gòu)Fig.2 One-dimensional signal reconstruction

表1 使用不同矩陣測量值重構(gòu)時間
Tab.1 Reconstruction time using different matrix measurements s

矩陣類型PEG生成矩陣G-PEG生成矩陣運行時間3.987 43.017 7

在一維信號仿真中，由圖2可以看出，G-PEG矩陣測量集和PEG矩陣測量集均能夠有效地恢復原始信號。以上結(jié)果驗證了稀疏校驗矩陣可以作為壓縮感知測量矩陣。表1給出了在不同矩陣測量值下對原始信號重構(gòu)100次的運行時間。由表1結(jié)果可以看出，在相同的條件下，使用G-PEG矩陣作為測量矩陣對于整體運行時間有著明顯改善，說明了G-PEG算法能夠有效提高矩陣的生成速度。

由圖3結(jié)果可以看出，在信號稀疏度相同的情況下，使用G-PEG構(gòu)造矩陣獲得的相同測量值具有比其他矩陣更高的重構(gòu)成功率。這是因為采用G-PEG構(gòu)造的矩陣，具有比其他測量矩陣更好的不相關(guān)性。

圖3 重構(gòu)成功率與測量數(shù)關(guān)系曲線圖Fig.3 Reconstruction power vs.Measurement number

圖4結(jié)果顯示，在保持測量數(shù)M相同的情況下，G-PEG生成矩陣獲得的測量集在相同重構(gòu)算法下具有比其他測量矩陣更高的重構(gòu)成功率，隨著信號稀疏度的增加，優(yōu)勢愈加明顯。

圖4 重構(gòu)成功率與稀疏度關(guān)系曲線圖Fig.4 Reconstruction power vs.Sparsity

表2展示了G-PEG算法構(gòu)造的測量矩陣與常用測量矩陣在使用相同重構(gòu)算法(OMP)時的誤差，對比得出：在相同的重構(gòu)條件下G-PEG生成矩陣能夠取得較好的重構(gòu)效果，對一維信號的重構(gòu)準確性稍弱于部分哈達瑪矩陣，但相較于部分哈達瑪矩陣有著更低的復雜度與存儲空間，這使得G-PEG算法構(gòu)造的測量矩陣在整體性能上優(yōu)于對比的隨機測量矩陣。

表2 一維信號重構(gòu)誤差比較
Tab.2 One-dimensional signal reconstruction error

矩陣類型循環(huán)矩陣G-PEG生成矩陣部分哈達瑪矩陣托普利茲矩陣伯努利矩陣高斯矩陣NMSE0.855 50.876 60.892 90.789 70.764 70.703 4

在二維圖像仿真中，采用指紋掃描圖像，尺寸為512×512，使用小波(wavelet)稀疏基，重構(gòu)算法為正交匹配追蹤(OMP)。

如圖5所示，對于二維圖像的重構(gòu)中，G-PEG生成矩陣優(yōu)勢明顯。主要是基于LDPC碼構(gòu)造矩陣其自身的稀疏性，在對于二維圖像的采樣中，相較于其他測量矩陣獲得測量值相關(guān)性更強，避免了信息的連續(xù)采樣。一維信號和二維圖像仿真結(jié)果表明，基于LDPC碼的稀疏測量矩陣不僅能夠滿足壓縮感知的采樣需求，并且在二維圖像的重構(gòu)過程中表現(xiàn)出更好的性能。這也驗證了G-PEG矩陣是一種性能優(yōu)良的測量矩陣。

圖5 不同測量矩陣重構(gòu)圖像比較Fig.5 Reconstruct image using different measurement matrix

表3 二維信號重構(gòu)誤差比較
Tab.3 Two-dimensional signal reconstruction error

矩陣類型循環(huán)矩陣G-PEG生成矩陣部分哈達瑪矩陣托普利茲矩陣伯努利矩陣高斯矩陣PSNR20.251 222.761 720.896 319.150 515.428 916.813 7

4 結(jié)束語

在壓縮感知的實際應(yīng)用場景中，測量矩陣在信號的采樣、壓縮、恢復環(huán)節(jié)扮演著重要角色。G-PEG矩陣在壓縮感知中的應(yīng)用，不僅驗證低密度奇偶校驗碼與壓縮感知間的理論聯(lián)系，同時為測量矩陣的研究提供了新的思路。在壓縮感知的應(yīng)用過程中，研究者應(yīng)考慮具體場景下的數(shù)據(jù)特征，構(gòu)造滿足要求的測量矩陣以提高壓縮感知的重構(gòu)效率。