基于马尔科夫链的随机测量矩阵研究

赵鸿图,李 成

(河南理工大学 物理与电子信息学院,河南 焦作 454000)

0 概述

随着无线通信技术的发展，信号处理过程中信号带宽日益增加，这使得以奈奎斯特采样定理为基础的传统信号处理方法对采样率的要求越来越高。2006年,CANDES和DONOHO提出的压缩感知理论[1]将采样和压缩两个过程合并为一个过程,打破了传统奈奎斯特采样理论对采样频率的限制,使得采样频率可以低于奈奎斯特采样频率,进而减少采样的数据量[2],节约存储资源。测量矩阵是压缩感知理论的中间环节,参与了信号的获取和重构过程的计算,对信号的重构效果有着较大的影响,其性能越好,重建信号与原信号之间的误差就越小,信号的恢复程度就越高[3-4]。近年来,许多学者提出了新的测量矩阵。文献[5]使用混沌序列构造测量矩阵,虽然该测量矩阵易于硬件实现,但由于混沌序列的取值需满足统计独立性,取值间隔要大于等于15,因此会产生大量的无用数据,造成存储空间的浪费。文献[6]提出基于奇异值分解的Toeplitz结构测量矩阵,相较于高斯随机矩阵和Toeplitz结构矩阵,使用该矩阵信号的重构精度得到了提高。本文使用马尔科夫链生成随机数[7],使得整个测量矩阵具有随机性,并采用对角矩阵与一般矩阵相结合的方式来构造测量矩阵。

1 测量矩阵

压缩感知理论的主要内容为:设f为N维可压缩信号,其稀疏变换为f=Ψs,Ψ是N×N维稀疏基,s是稀疏变换信号,通过M×N维测量矩阵(M<

(1)

在求得s后,可重构出信号f,由于此问题的计算是一个NP-hard问题,通常使用l1范数来代替l0范数求解[8-9]。

在压缩感知理论中,为能够准确地重构出原始信号,要求测量矩阵满足有限等距性质(Restricted Isometry Property,RIP)[10-11],RIP表示为:

(2)

其中,εk∈(0,1),称为RIP常数。

由于在验证矩阵是否满足RIP特性时需要进行大量计算,验证该问题变得十分困难,因此需要找到RIP特性的替代条件来解决该问题。文献[12]指出低相关性的矩阵满足RIP特性。本文根据该关系构造测量矩阵,并通过仿真得到相关数据,与常用的一些测量矩阵和基于奇异值分解的Toeplitz结构矩阵进行比较。

常用的高斯随机矩阵[13-14]、伯努利矩阵[14-15]等属于随机测量矩阵的范畴,此类矩阵重构精度较高,但需要的存储空间及时间复杂度较大,对硬件的要求较高。确定性测量矩阵包括多项式矩阵、Toeplitz矩阵[14,16]等,此类矩阵需要的存储空间较小,构造速度较快,且易于硬件的实现,但重构效果一般。部分随机测量矩阵包括部分阿达玛矩阵[14,17]、部分傅里叶矩阵等,此类矩阵同时具有随机性和确定性,其重构的图像效果较好,但因其需要从正交的高阶方阵中随机抽取行来构造矩阵,因此会造成存储资源的浪费。

2 基于马尔科夫链的测量矩阵构造

2.1 马尔科夫链

马尔科夫链描述了一种状态序列,其每个状态值都取决于前面有限个状态。马尔科夫链是具有马尔科夫性质的随机变量X1,X2,…的一个数列。这些变量的范围,即它们所有可能取值的集合,被称为“状态空间”,Xn的值则是在时间n中的状态。如果Xn+1对于过去状态的条件概率分布仅是Xn的一个函数,则P(Xn+1=x|X1=x1,X2=x2,…,Xn=xn)=P(Xn+1=x|Xn=xn),其中x为过程中的某个状态。该恒等式可以被看作是马尔科夫性质。

2.2 基于马尔科夫链的随机测量矩阵

为构造一个随机测量矩阵,将马尔科夫链生成的随机数作为测量矩阵中的元素,使得测量矩阵具有随机性。又为使测量矩阵满足RIP特性,需最大程度地保证构造矩阵各列向量之间的非相关性。因此,本文提出将M×M维测量矩阵构造成M×M维对角阵与M×(N-M)维矩阵相结合的形式。

当对角阵主对角线上的元素全都不为0时,即rank(D)=M,此时对角阵的行向量与列向量之间都是线性无关的。为使主对角线上的元素均不为0,在使用马尔科夫链生成随机数bl,l=1,2,…,M后,将随机数按照规则分别映射为-1和1[11],映射规则为:

(3)

将此数值作为测量矩阵Φ的前M个列向量,即:

(4)

剩余的N-M个列向量也由马尔科夫链产生的随机数经过映射后构成。马尔科夫链生成M×(N-M)个随机数e1,e2,…,eM×(N-M),由于设置状态空间内的数有正负性,因此在设置状态空间时,生成服从标准正态分布的随机数作为状态空间内的数。根据规则将这些随机数分别映射为1和0,具体映射规则为:

(5)

其中,gi,i=1,2,…,M×(N-M)为随机数经过映射后得到的结果,由其构成测量矩阵的N-M个列向量φk,k=M+1,M+2,…,N。

(6)

由式(4)与式(6)合成测量矩阵:

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

(7)

将矩阵按列进行归一化得到实际应用的测量矩阵Φ。归一化公式如下:

(8)

测量矩阵被构造成一个对角阵和一般矩阵相组合的形式,矩阵的秩为M,相较于常用的测量矩阵而言,减少了计算量与存储空间。

3 实验结果与分析

本文实验的环境为Intel Core i3 CPU,64位Windows 7.0操作系统,使用的仿真软件为MATLAB R2014a。为验证本文矩阵的可靠性和有效性,使用标准图像lena、baboon、peppers、house。图像的尺寸为256像素×256像素,重构算法为正交匹配追踪算法(Orthogonal Matching Pursuit,OMP)[18-19],分别使用多种常用的测量矩阵和本文矩阵进行仿真,并且从文献[6]中可以直接得到基于奇异值分解的Toeplitz结构矩阵的仿真数据,与本文仿真结果进行对比。为降低随机性因素的影响,本文得到的数据都是在100次实验后求得的平均值。将峰值信噪比(Peak Signal to Noise Ratio,PSNR)和重构时间t作为算法的评价标准[20-21]。PSNR的计算公式为:

(9)

重构时间t为:

t=te-ts

(10)

其中,te是结束时间,ts是开始时间。

平均重构时间为:

(11)

其中,L为重构次数。

从图1～图8的仿真结果可以看出,当压缩比相同时,使用本文矩阵的重构效果最好。

图1 压缩比为70%时lena图像重构对比Fig.1 Comparison of lena image reconstruction whenthe compression ratio is 70%

图2 压缩比为70%时baboon图像重构对比Fig.2 Comparison of baboon image reconstruction whenthe compression ratio is 70%

图3 压缩比为70%时peppers图像重构对比Fig.3 Comparison of peppers image reconstruction whenthe compression ratio is 70%

图4 压缩比为70%时house图像重构对比Fig.4 Comparison of house image reconstruction whenthe compression ratio is 70%

图5 压缩比为50%时lena图像重构对比Fig.5 Comparison of lena image reconstruction whenthe compression ratio is 50%

图6 压缩比为50%时baboon图像重构对比Fig.6 Comparison of baboon image reconstruction whenthe compression ratio is 50%

图7 压缩比为50%时peppers图像重构对比Fig.7 Comparison of peppers image reconstruction whenthe compression ratio is 50%

图8 压缩比为50%时house图像重构对比Fig.8 Comparison of house image reconstruction whenthe compression ratio is 50%

表1、表2为使用各测量矩阵对4种图像进行仿真后得到的数据,其中“—”表示文献[6]对该类数据未进行仿真,从两表中的数据可以看出,当压缩比为70%时,重构图像的PSNR在使用本文矩阵与部分阿达玛矩阵时最高。当压缩比变为50%时,使用本文矩阵时重构图像的PSNR最高。本文矩阵的平均重构时间与常用测量矩阵的重构时间十分接近,能够满足实际的应用需求。图9表示压缩比小于50%时,各种矩阵对lena进行仿真后的PSNR。

本文测量矩阵使用对角阵与一般矩阵相结合的形式，对角阵元素根据规则分别映射成 1和1，一般矩阵中的元素又根据正负性分别映射成1和0，在压缩比相同的情况下，使用本文矩阵进行压缩感知所得到的PSNR要高于高斯随机矩阵和伯努利矩阵。Toeplitz矩阵属于确定性测量矩阵，此类矩阵虽然在硬件上容易实现，具有较高的实用性，但是重构效果一般。学者针对此缺点对Toeplitz矩阵加以改进，提出基于奇异值分解的Toeplitz结构矩阵，但通过仿真结果可知效果仍差于本文矩阵。部分随机测量矩阵虽然重构效果较好，但浪费存储资源的情况比较严重。

表1 压缩比为70%时测量矩阵的性能对比结果Table 1 Performance comparison results of measurement matrixes when compression ratio is 70%

表2 压缩比为50%时测量矩阵的性能对比结果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 结束语

本文构造一种新的压缩感知测量矩阵,考虑到对角阵具有良好的正交性和线性非相关性,采用对角阵与一般矩阵相结合的形式得到M×N维压缩感知测量矩阵,使用马尔科夫链生成随机数,并将随机数按照两种规则进行映射,映射后的结果作为两部分矩阵中的元素。仿真结果表明,在压缩比相同的条件下,本文提出测量矩阵的PSNR比其他测量矩阵高出约2 dB～3 dB。下一步可将压缩感知技术与变分法和分数阶Fourier变换法相结合，应用于图像去噪及磁共振成像问题研究中。