一種基于PEG的構造矩陣在壓縮感知中的應用

杜鳳強，葉 潤，閆 斌

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

0 引言

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

1 壓縮感知

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

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

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

(1)

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

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

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

(2)

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

(3)

(4)

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

2 LDPC碼與壓縮感知的聯系

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

圖1 分組碼結構Fig.1 Structure of block code

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

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

(5)

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

(6)

(7)

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

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

(8)

問題CD2的求解復雜度是指數級的，Feldman[9-10]對以上問題的求解進行了轉化，對Ccc的凸包(Convex Hull)conv(Ccc)進行了擴展，轉而尋找問題的最優解，降低了求解的復雜度。

(9)

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

(10)

(11)

其中

(12)

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

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

(13)

(14)

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

(15)

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

3 G-PEG測量矩陣

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

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

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

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

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

圖2 一維信號重構Fig.2 One-dimensional signal reconstruction

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

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

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

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

圖3 重構成功率與測量數關系曲線圖Fig.3 Reconstruction power vs.Measurement number

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

圖4 重構成功率與稀疏度關系曲線圖Fig.4 Reconstruction power vs.Sparsity

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

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

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

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

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

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

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

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

4 結束語

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