ABSTRACT

The measurement matrix as the core of the compressed sensing theory, will have a significant impact on the measurement and reconstruction. This paper produces a method of compressed sensing measurement matrix through the m sequences. First of all, it gives a method to construct the measurement matrix with compression rate is 0.5; this measurement matrix has small element set and certain cycle characteristics. Secondly, for combining the theory of finite fields, the measurement matrix based on m sequence is further improved. The compression rate of the matrix measurement range is greatly increased. The simulation results show that the measurement matrix is constructed in this paper which is better than Gause measurement matrix reconstruction performance of the same size, avoids the random measurement matrix uncertainty and has a certain practical value.

Keywords:Compressed Sensing, Measurement Matrix, m Sequences, RIP, Column Correlation

基于m序列的压缩感知测量矩阵构造

李明，江桦，裴立业

解放军信息工程大学信息系统工程学院，河南 郑州

收稿日期：2016年3月30日；录用日期：2016年4月19日；发布日期：2016年4月22日

摘 要

测量矩阵作为压缩感知理论的核心内容，对信号的测量和重构会产生重大影响。本文主要基于m序列构造压缩感知测量矩阵。首先，给出一种压缩率为0.5的测量矩阵构造方法，利用该方法构造的测量矩阵元素取值集合较小，具有一定的循环特性。其次，结合有限域的理论，对利用m序列构造的测量矩阵做进一步改进，改进后测量矩阵的压缩率取值范围增大加。仿真结果表明：本文构造的测量矩阵的重构性能优于同大小的Gause测量矩阵，避免了随机性测量矩阵的不确定性，具有一定实用价值。

关键词 :压缩感知，测量矩阵，m序列，RIP，列相关性

1. 引言

压缩感知理论主要包含信号的稀疏表示、测量矩阵的构造和重建算法的设计三个方面的内容，其中，测量矩阵的构造是压缩感知理论的关键问题 [1] - [3] 。测量信号是否包含了原始信号的足够信息决定着能否精确重构，且测量矩阵的好坏对后端的重构也有很大的作用。在压缩感知理论中，对测量矩阵矩阵的约束并不是非常严格的，Donoho在文献 [4] 中给出的CS1-CS3三个条件表明大部分一致分布的随机矩阵都可作为测量矩阵。2005年，E Candès和T. Tao共同给出了测量矩阵的有限等距性质(Restricted Isometry Property，简称RIP) [5] 。利用RIP性质可以用来证明一个矩阵是否可以作为测量矩阵，RIP性质被公认为是关于测量矩阵的一个重要理论。除RIP外，可用来衡量某一矩阵是否能作为测量矩阵还有其它一些理论，例如零空间条件 [6] 、相关性理论 [7] 等。

测量矩阵按照产生方式，可划分为随机性、部分随机性和确定性三类。Gause测量矩阵和Bernoulli测量矩阵属于随机性的测量矩阵，在理论上被证明都可以用做测量矩阵，但具体电路实现起来复杂，占用大量存储资源，而且只在概率统计意义下满足重构要求，并不能保证每一次的测量都包含了信号的全部信息。部分随机性的测量矩阵相比随机性的测量矩阵减少了一些随机性，大多数情况下是行随机，主要有部分Fourier矩阵和部分Hadamard矩阵。他们的基本构造思路都是从正交方阵中随机性地抽取行来构造量矩阵，可以证明，这两种测量矩阵都在较高概率下具有一定阶数的RIP 特性，满足压缩感知对测量矩阵的要求，但是随机抽取行的方法仍有导致测量失败的可能。压缩感知理论被提出后，很多学者对确定性的测量矩阵的构造进行了研究。文献 [8] 提出通过利用有限域中多项式的取值构造了 (为素数，为自然数)的测量矩阵；文献 [9] - [12] 都是利用混沌序列来构造测量矩阵，从仿真实验的结果来看，比同等大小的Gause测量矩阵效果要好，但利用混沌序列构造的测量矩阵仍是稠密的，占用存储空间较多；文献 [13] 基于离散Chirp编码构造了的测量矩阵，重构性能与Gause测量矩阵相当，但不适用于维数过小的情况；文献 [14] 利用二阶Reed-Muller码构造了的测量矩阵；文献 [15] [16] 基于好的低密度奇偶校验码(LDPC)来构造测量矩阵，但对矩阵的行、列数要求严格。本文利用m序列构造了一种压缩率为0.5的测量矩阵，从理论上证明了该矩阵可以作为测量矩阵使用，并结合有限域的理论对其进一步扩展，扩展后测量矩阵行、列取值相对更加自由，可适应的压缩率范围大大提高。仿真实验表明本文所提出的测量矩阵优于同等大小的Gause测量矩阵，具有一定的循环特性和稀疏性，有一定实用价值。

2. 基本理论

为便于叙述，这里将信号抽象记为一个维向量，稀疏性指的是信号中非0元素的个数较少。稀疏信号的集合用表示，，其中表示中非0值数目，当时，称满足阶稀疏性。对进行压缩观测即是：

(1)

其中，是一个的矩阵，称为测量矩阵，是维的观测值，称为测量次数，称为压缩率。压缩测量的过程实际是将一个维的向量投影到一个维空间上，若是投影中包含重构需要的所有信息时，利用来恢复是有可能的。对于(1)式，当时，是一个求解欠定线性方程组问题，一般情况下有无穷多组解。当我们增加了满足阶稀疏性的这个前提条件后，只需再对做一些要求和改变，确定唯一的是有可能的。文献 [17] 指出：在满足阶稀疏性的前提下，若的任意列都线性无关，通过求解如下的问题：

(2)

可获得一个关于的唯一确定解，这个确保唯一性的条件也是容易理解的，但这个求解问题是一个NP-hard问题。当满足零空间特性或是一定阶数的RIP特性时，该问题可进一步转化为如下问题的求解：

(3)

问题属于一个凸优化问题，可以利用线形规划的一些现有办法来求解，其中RIP特性 [5] 定义如下：如果存在常数，使得

(4)

对任意都成立，则称满足阶RIP特性，称为RIP常数。

文献 [18] 指出，若满足阶RIP特性，且RIP常数时，那么对于任意，用矩阵对信号进行测量，根据观测值可唯一重构出信号。

式(4)给出了RIP特性的定义，RIP特性是一个验证测量矩阵能否用于压缩感知的有力工具，但是验证一个矩阵的RIP特性仍是一个NP-hard问题，且RIP特性仍是个充分条件，并不是必要条件。Gause测量矩阵被证明满足RIP特性，作为测量矩阵可行，但是真正的随机性测量矩阵实现起来十分困难，并不能保证每一次具体的测量能够满足重构。

易知，一个矩阵的列相干性是相对容易计算的。对于矩阵，定义其列相干性为：

(5)

文献 [19] 给出了列相干性的一个下界，称为Welch界：

(6)

文献 [7] 指出：若矩阵的列相干性为，那么满足RIP常数为：

(7)

的阶RIP特性。本文主要从矩阵的列相干性出发考虑，利用m序列来构造测量矩阵。

3. 基于m序列的测量矩阵构造

在扩频通信和密码学理论中，具有良好的相关特性的序列一直是研究的热点，序列的互相关函数的定义如下：

(8)

其中序列和的周期为，的下标按照模运算。当时，称为序列在位移为时的周期自相关函数。

利用反馈移位寄存器设计序列的方法有比较直观的实现电路，所以该设计方法较其他序列的设计方法相对更为容易理解，m序列就是一种反馈移位寄存器序列，又称为最长线性反馈移位寄存器序列。

m序列的定义如下 [20] ：

设是上的线形反馈移位寄存器的连接多项式：

(9)

当且仅当是上的本原多项式时，则中的全体非零序列都是m序列。

对于二元m序列 (即m序列的元素在集合{+1，−1}中取值)，具有以下性质：

1) 周期性：

序列的周期长度为，其中为自然数。

2) 自相关特性：

对于周期长度为的m序列，其自相关函数为：

(10)

3) 平衡性：

序列中+1和−1的个数几乎相等，只相差1个。

构造测量矩阵如下：

(11)

周期为的m序列构成矩阵的第一列，从第2列到第列依次是序列的循环左移位，第列到第列分别是从第1列到第列的倍循环采样，(这里取采样周期为，每次采样只采到一个值)。

计算矩阵的列相干性：

当都在前列取时，；当都在后列取时，；当分别在前列、后列取时，；

综上，测量矩阵的列相干性为。

进而据式(7)可推得该测量矩阵满足的阶RIP特性，当时，对于稀疏度不大于的信号，可保证精确重构。由于RIP特性是充分条件，并非充要条件，所以推测能够精确重构的信号的稀疏度可能会大于，下节仿真实验的结果也证实了这个猜测。

按照式(11)所构造测量矩阵的大小为，压缩率固定为，只能取2的幂指数，行、列的取值范围受限。

De Vore在文献 [8] 利用有限域中多项式的取值，构造出了 (为素数，为自然数)的确定性测量矩阵。测量矩阵的元素在{0，1}中取值，且具有一个很好的性质：当时，该矩阵的每一列都只有个1，且任意两列相同位置出现1的个数为1，通俗的说，即求任意两列的内积时仅有一个1对上，其余要么是0和0对上，要么是0和1对上。

根据有限域的理论可知，将素数替换为 (是2的幂数，即)时，DeVore提出的方法依然有效。即取时，构造出的测量矩阵的每一列都只有个1，且任意两列相同位置出现1的个数为1，矩阵分析理论中，Kronecker直积是一种十分重要的概念。其定义如下：对于矩阵和，、的Kronecker直积记为等于：

(12)

Kronecker直积具有一个很好的性质：若矩阵、都是正交矩阵，则也是正交矩阵。这里将Kronecker直积作些改变，当时，将直积中用替换，即原来是用整个矩阵替换，这里用矩阵的某一行来替换；当时，将直积中用0替换。若矩阵中每一列非零值的个数不小于矩阵的行数时，这种替换是可行的。为了下面方便的叙述，将这种替换记为运算。

取式(11)中矩阵的前列构成的子矩阵(矩阵大小为)做为矩阵，参照De Vore在文献 [8] 中提出的方法构造的矩阵 (矩阵大小为)做为矩阵，然后依运算可构造出新的测量矩阵 (大小为，压缩率为)：

(13)

与式(12)相比较，在式(13)中，的位置，仍为0；的位置换成，其中代表矩阵的行向量。

根据式(5)，计算式(13)中的测量矩阵的列相干性：

1) 当来自矩阵的同一个时

此时都来自同一个矩阵，且的结构未发生变化，所以列相干性等于矩阵的列相干性，式(11)中前列构成的子矩阵的列相干性为，所以此时的。

2) 当来自矩阵的不同的， ()时，相对于原矩阵在矩阵的位置结构发生了变化，但仅有一组+1或者-1能够对上，其他都错开了所以式(5)中分子的最大值为1，而分母仍为，所以此时列相干性为。

综上分析：

测量矩阵的列相干性。

根据式(6)大小为的矩阵的Welch界为：，可见本文构造的测量矩阵基本已经比较接近Welch界，元素取值在{-1，0，+1}取值，较为单一，且具有一定的循环特性和稀疏性，有利于硬件产生。

4. 仿真实验

实验(1)：对一维稀疏信号进行测量和恢复

I) 压缩率。选取周期为的m序列作为初始序列，按照式(11)生成大小为255×510的测量矩阵，与同等大小的Gause测量矩阵对一维稀疏信号进行测量重构。每一个稀疏度，采用OMP算法重构1000次，得到重构概率与稀疏度的对应曲线，如图1所示。

从图1可以看出，基于m序列构造的测量矩阵重构性能优于同等大小Gause测量矩阵，且能精确重构的信号的稀疏度比理论值要大，稀疏度为58时，本文所提出测量矩阵仍可以精确重构。

II) 压缩率。分别选取周期为和的m序列作为初始序列，按照式(11)生成挑选其前列列作为，再与Devore提出的确定性矩阵结合，按照式(13)生成64 × 512和256 × 4096的测量矩阵，然后分别与同等大小的Gause测量矩阵对一维稀疏信号进行测量重构。每一个稀疏度，采用OMP算法重构1000次，得到重构概率与稀疏度的对应曲线，如图2所示。

从图2和图3可以看出，利用m序列构造的测量矩阵能精确重构的信号稀疏度均比同等大小Gause测量矩阵要大。

实验(2)：对“cameraman”图像进行测量和恢复。

选取512 × 512的“cameraman”图像，稀疏基取DCT基，分别采用64 × 512、256 × 512的测量矩阵和同等大小的Gause测量矩阵对该图像逐行测量和恢复。重构算法仍选择OMP算法。恢复结果如图4所示。

从图4来看，直观上基于m序列构造的测量矩阵比Gause测量矩阵恢复的更为清晰。为了进一步说明图4的实验结果，表1列举了两种测量矩阵峰值信噪比(PSNR)的对比。

表1. “cameraman”图像重构的PSNR值

图1. 重构概率随稀疏度变化的对比曲线

图2. 矩阵大小为64 × 512

图3. 矩阵大小为256 × 4906

图4. “cameraman”图像重构效果对比图

表1也说明基于m序列构造的测量矩阵的重构性能优于Gause测量矩阵。

5. 结束语

本文基于m序列构造的测量矩阵的列相干性接近于Welch界，元素取值较为单一，且具有一定的循环特性，有利于硬件实现。仿真实验的结果显示基于m序列构造的测量矩阵的性能优于同大小的Gause测量矩阵。本文从矩阵的列相干性出发设计测量矩阵，本质上是借助于RIP特性，但RIP特性并非充要条件，所以寻找压缩感知测量矩阵的充要条件，继而根据充要条件才可能设计出更优的测量矩阵；其次基于m序列构造的测量矩阵可任意删列来改变压缩率，但行的取值仍比较受限，而Gause测量矩阵的行、列选取均任意，所以寻找行、列取值更加自由的测量矩阵仍需进一步研究。

文章引用

李 明,江 桦,裴立业. 基于m序列的压缩感知测量矩阵构造
Construction of Compressed Sensing Matrixs Based on m Sequences[J]. 无线通信, 2016, 06(02): 52-60. http://dx.doi.org/10.12677/HJWC.2016.62008

参考文献 (References)