基于馬爾科夫鏈的隨機測量矩陣研究

趙鴻圖,李 成

(河南理工大學(xué) 物理與電子信息學(xué)院,河南 焦作 454000)

0 概述

隨著無線通信技術(shù)的發(fā)展，信號處理過程中信號帶寬日益增加，這使得以奈奎斯特采樣定理為基礎(chǔ)的傳統(tǒng)信號處理方法對采樣率的要求越來越高。2006年,CANDES和DONOHO提出的壓縮感知理論[1]將采樣和壓縮兩個過程合并為一個過程,打破了傳統(tǒng)奈奎斯特采樣理論對采樣頻率的限制,使得采樣頻率可以低于奈奎斯特采樣頻率,進而減少采樣的數(shù)據(jù)量[2],節(jié)約存儲資源。測量矩陣是壓縮感知理論的中間環(huán)節(jié),參與了信號的獲取和重構(gòu)過程的計算,對信號的重構(gòu)效果有著較大的影響,其性能越好,重建信號與原信號之間的誤差就越小,信號的恢復(fù)程度就越高[3-4]。近年來,許多學(xué)者提出了新的測量矩陣。文獻[5]使用混沌序列構(gòu)造測量矩陣,雖然該測量矩陣易于硬件實現(xiàn),但由于混沌序列的取值需滿足統(tǒng)計獨立性,取值間隔要大于等于15,因此會產(chǎn)生大量的無用數(shù)據(jù),造成存儲空間的浪費。文獻[6]提出基于奇異值分解的Toeplitz結(jié)構(gòu)測量矩陣,相較于高斯隨機矩陣和Toeplitz結(jié)構(gòu)矩陣,使用該矩陣信號的重構(gòu)精度得到了提高。本文使用馬爾科夫鏈生成隨機數(shù)[7],使得整個測量矩陣具有隨機性,并采用對角矩陣與一般矩陣相結(jié)合的方式來構(gòu)造測量矩陣。

1 測量矩陣

壓縮感知理論的主要內(nèi)容為:設(shè)f為N維可壓縮信號,其稀疏變換為f=Ψs,Ψ是N×N維稀疏基,s是稀疏變換信號,通過M×N維測量矩陣(M<

(1)

在求得s后,可重構(gòu)出信號f,由于此問題的計算是一個NP-hard問題,通常使用l1范數(shù)來代替l0范數(shù)求解[8-9]。

在壓縮感知理論中,為能夠準確地重構(gòu)出原始信號,要求測量矩陣滿足有限等距性質(zhì)(Restricted Isometry Property,RIP)[10-11],RIP表示為:

(2)

其中,εk∈(0,1),稱為RIP常數(shù)。

由于在驗證矩陣是否滿足RIP特性時需要進行大量計算,驗證該問題變得十分困難,因此需要找到RIP特性的替代條件來解決該問題。文獻[12]指出低相關(guān)性的矩陣滿足RIP特性。本文根據(jù)該關(guān)系構(gòu)造測量矩陣,并通過仿真得到相關(guān)數(shù)據(jù),與常用的一些測量矩陣和基于奇異值分解的Toeplitz結(jié)構(gòu)矩陣進行比較。

常用的高斯隨機矩陣[13-14]、伯努利矩陣[14-15]等屬于隨機測量矩陣的范疇,此類矩陣重構(gòu)精度較高,但需要的存儲空間及時間復(fù)雜度較大,對硬件的要求較高。確定性測量矩陣包括多項式矩陣、Toeplitz矩陣[14,16]等,此類矩陣需要的存儲空間較小,構(gòu)造速度較快,且易于硬件的實現(xiàn),但重構(gòu)效果一般。部分隨機測量矩陣包括部分阿達瑪矩陣[14,17]、部分傅里葉矩陣等,此類矩陣同時具有隨機性和確定性,其重構(gòu)的圖像效果較好,但因其需要從正交的高階方陣中隨機抽取行來構(gòu)造矩陣,因此會造成存儲資源的浪費。

2 基于馬爾科夫鏈的測量矩陣構(gòu)造

2.1 馬爾科夫鏈

馬爾科夫鏈描述了一種狀態(tài)序列,其每個狀態(tài)值都取決于前面有限個狀態(tài)。馬爾科夫鏈是具有馬爾科夫性質(zhì)的隨機變量X1,X2,…的一個數(shù)列。這些變量的范圍,即它們所有可能取值的集合,被稱為“狀態(tài)空間”,Xn的值則是在時間n中的狀態(tài)。如果Xn+1對于過去狀態(tài)的條件概率分布僅是Xn的一個函數(shù),則P(Xn+1=x|X1=x1,X2=x2,…,Xn=xn)=P(Xn+1=x|Xn=xn),其中x為過程中的某個狀態(tài)。該恒等式可以被看作是馬爾科夫性質(zhì)。

2.2 基于馬爾科夫鏈的隨機測量矩陣

為構(gòu)造一個隨機測量矩陣,將馬爾科夫鏈生成的隨機數(shù)作為測量矩陣中的元素,使得測量矩陣具有隨機性。又為使測量矩陣滿足RIP特性,需最大程度地保證構(gòu)造矩陣各列向量之間的非相關(guān)性。因此,本文提出將M×M維測量矩陣構(gòu)造成M×M維對角陣與M×(N-M)維矩陣相結(jié)合的形式。

當對角陣主對角線上的元素全都不為0時,即rank(D)=M,此時對角陣的行向量與列向量之間都是線性無關(guān)的。為使主對角線上的元素均不為0,在使用馬爾科夫鏈生成隨機數(shù)bl,l=1,2,…,M后,將隨機數(shù)按照規(guī)則分別映射為-1和1[11],映射規(guī)則為:

(3)

將此數(shù)值作為測量矩陣Φ的前M個列向量,即:

(4)

剩余的N-M個列向量也由馬爾科夫鏈產(chǎn)生的隨機數(shù)經(jīng)過映射后構(gòu)成。馬爾科夫鏈生成M×(N-M)個隨機數(shù)e1,e2,…,eM×(N-M),由于設(shè)置狀態(tài)空間內(nèi)的數(shù)有正負性,因此在設(shè)置狀態(tài)空間時,生成服從標準正態(tài)分布的隨機數(shù)作為狀態(tài)空間內(nèi)的數(shù)。根據(jù)規(guī)則將這些隨機數(shù)分別映射為1和0,具體映射規(guī)則為:

(5)

其中,gi,i=1,2,…,M×(N-M)為隨機數(shù)經(jīng)過映射后得到的結(jié)果,由其構(gòu)成測量矩陣的N-M個列向量φk,k=M+1,M+2,…,N。

(6)

由式(4)與式(6)合成測量矩陣:

Φ=(φ1,φ2,…,φM,φM+1,φM+2,…,φN)=

(7)

將矩陣按列進行歸一化得到實際應(yīng)用的測量矩陣Φ。歸一化公式如下:

(8)

測量矩陣被構(gòu)造成一個對角陣和一般矩陣相組合的形式,矩陣的秩為M,相較于常用的測量矩陣而言,減少了計算量與存儲空間。

3 實驗結(jié)果與分析

本文實驗的環(huán)境為Intel Core i3 CPU,64位Windows 7.0操作系統(tǒng),使用的仿真軟件為MATLAB R2014a。為驗證本文矩陣的可靠性和有效性,使用標準圖像lena、baboon、peppers、house。圖像的尺寸為256像素×256像素,重構(gòu)算法為正交匹配追蹤算法(Orthogonal Matching Pursuit,OMP)[18-19],分別使用多種常用的測量矩陣和本文矩陣進行仿真,并且從文獻[6]中可以直接得到基于奇異值分解的Toeplitz結(jié)構(gòu)矩陣的仿真數(shù)據(jù),與本文仿真結(jié)果進行對比。為降低隨機性因素的影響,本文得到的數(shù)據(jù)都是在100次實驗后求得的平均值。將峰值信噪比(Peak Signal to Noise Ratio,PSNR)和重構(gòu)時間t作為算法的評價標準[20-21]。PSNR的計算公式為:

(9)

重構(gòu)時間t為:

t=te-ts

(10)

其中,te是結(jié)束時間,ts是開始時間。

平均重構(gòu)時間為:

(11)

其中,L為重構(gòu)次數(shù)。

從圖1～圖8的仿真結(jié)果可以看出,當壓縮比相同時,使用本文矩陣的重構(gòu)效果最好。

圖1 壓縮比為70%時lena圖像重構(gòu)對比Fig.1 Comparison of lena image reconstruction whenthe compression ratio is 70%

圖2 壓縮比為70%時baboon圖像重構(gòu)對比Fig.2 Comparison of baboon image reconstruction whenthe compression ratio is 70%

圖3 壓縮比為70%時peppers圖像重構(gòu)對比Fig.3 Comparison of peppers image reconstruction whenthe compression ratio is 70%

圖4 壓縮比為70%時house圖像重構(gòu)對比Fig.4 Comparison of house image reconstruction whenthe compression ratio is 70%

圖5 壓縮比為50%時lena圖像重構(gòu)對比Fig.5 Comparison of lena image reconstruction whenthe compression ratio is 50%

圖6 壓縮比為50%時baboon圖像重構(gòu)對比Fig.6 Comparison of baboon image reconstruction whenthe compression ratio is 50%

圖7 壓縮比為50%時peppers圖像重構(gòu)對比Fig.7 Comparison of peppers image reconstruction whenthe compression ratio is 50%

圖8 壓縮比為50%時house圖像重構(gòu)對比Fig.8 Comparison of house image reconstruction whenthe compression ratio is 50%

表1、表2為使用各測量矩陣對4種圖像進行仿真后得到的數(shù)據(jù),其中“—”表示文獻[6]對該類數(shù)據(jù)未進行仿真,從兩表中的數(shù)據(jù)可以看出,當壓縮比為70%時,重構(gòu)圖像的PSNR在使用本文矩陣與部分阿達瑪矩陣時最高。當壓縮比變?yōu)?0%時,使用本文矩陣時重構(gòu)圖像的PSNR最高。本文矩陣的平均重構(gòu)時間與常用測量矩陣的重構(gòu)時間十分接近,能夠滿足實際的應(yīng)用需求。圖9表示壓縮比小于50%時,各種矩陣對lena進行仿真后的PSNR。

本文測量矩陣使用對角陣與一般矩陣相結(jié)合的形式，對角陣元素根據(jù)規(guī)則分別映射成 1和1，一般矩陣中的元素又根據(jù)正負性分別映射成1和0，在壓縮比相同的情況下，使用本文矩陣進行壓縮感知所得到的PSNR要高于高斯隨機矩陣和伯努利矩陣。Toeplitz矩陣屬于確定性測量矩陣，此類矩陣雖然在硬件上容易實現(xiàn)，具有較高的實用性，但是重構(gòu)效果一般。學(xué)者針對此缺點對Toeplitz矩陣加以改進，提出基于奇異值分解的Toeplitz結(jié)構(gòu)矩陣，但通過仿真結(jié)果可知效果仍差于本文矩陣。部分隨機測量矩陣雖然重構(gòu)效果較好，但浪費存儲資源的情況比較嚴重。

表1 壓縮比為70%時測量矩陣的性能對比結(jié)果Table 1 Performance comparison results of measurement matrixes when compression ratio is 70%

表2 壓縮比為50%時測量矩陣的性能對比結(jié)果Table 2 Performance comparison results of measurement matrixes when compression ratio is 50%

圖9 壓縮比小于50%時測量矩陣峰值信噪比Fig.9 PSNR of measurement matrixes when the compressionratio is less than 50%

4 結(jié)束語

本文構(gòu)造一種新的壓縮感知測量矩陣,考慮到對角陣具有良好的正交性和線性非相關(guān)性,采用對角陣與一般矩陣相結(jié)合的形式得到M×N維壓縮感知測量矩陣,使用馬爾科夫鏈生成隨機數(shù),并將隨機數(shù)按照兩種規(guī)則進行映射,映射后的結(jié)果作為兩部分矩陣中的元素。仿真結(jié)果表明,在壓縮比相同的條件下,本文提出測量矩陣的PSNR比其他測量矩陣高出約2 dB～3 dB。下一步可將壓縮感知技術(shù)與變分法和分數(shù)階Fourier變換法相結(jié)合，應(yīng)用于圖像去噪及磁共振成像問題研究中。