APP下载

压缩感知中测量矩阵构造综述

2017-04-17张培林王怀光杨望灿陈彦龙

计算机应用 2017年1期
关键词:字典重构定义

王 强,张培林,王怀光,杨望灿,陈彦龙

(军械工程学院 车辆与电气工程系,石家庄 050003)

(*通信作者电子邮箱ZPL1955@163.com)

压缩感知中测量矩阵构造综述

王 强,张培林*,王怀光,杨望灿,陈彦龙

(军械工程学院 车辆与电气工程系,石家庄 050003)

(*通信作者电子邮箱ZPL1955@163.com)

压缩感知测量矩阵构造方式多样并不断发展,为梳理现有研究成果,掌握测量矩阵发展动态,对压缩感知测量矩阵构造进行系统介绍。首先,针对传统信号采集理论存在的信息冗余问题,阐述了压缩感知理论在信号采集过程中资源利用率高、存储空间小的优势;其次,以压缩感知理论框架为基础,从测量矩阵构造原则、测量矩阵产生方法、测量矩阵结构设计、测量矩阵优化方法四个方面,对压缩感知测量矩阵构造进行分析,讨论了测量矩阵构造过程中不同原则、结构、方法的优势;最后,在总结现有研究成果的基础上,对测量矩阵的发展方向进行了展望。

压缩感知;测量矩阵;有限等距性质;信号重构;信号采集

0 引言

在传统奈奎斯特采样定理条件下,要实现原始信号的精确重构,采样过程中的采样频率至少高于原始信号中最高频率的两倍。但奈奎斯特采样定理是原始信号能够精确重构的充分条件,而非必要条件。依照该定理采样后的数据中包含大量冗余信息,数据在应用过程中,经过处理只保留了部分有用信息,大部分无用信息被舍弃,这就导致在采样、压缩过程中,大量时间、空间被浪费。因此学者们尝试突破奈奎斯特采样定理的限制,提出利用少量的采样数据来精确重构原始信号。Candes等[1-2]在压缩感知理论上取得重大突破。他们结合随机矩阵,利用少量随机采样的频率系数,通过求解一个凸优化问题,实现了原始信号的精确重构[3],并提出了鲁棒的不确定性原则。随后,压缩感知的理论被正式提出,并得到了不断的完善、发展与应用[4]。在压缩感知条件下,某个变换域具有稀疏、近稀疏性的信号或者图像,可以通过“全息”测量的方式,将采样与压缩的过程合并,直接获得原始信号的有用信息,并能够通过近似优化算法,实现原始信号的精确重构[5]。

压缩感知理论主要包括信号稀疏表示、测量矩阵构造、重构算法设计三方面的内容[6]。在压缩感知理论中,要求信号具有可压缩性,信号的稀疏表示是信号可压缩性能的具体体现,而可压缩性能的好坏依赖于稀疏字典的设计,在压缩感知之初,信号的稀疏字典是基于变换域(傅里叶变换、小波变换等)的正交基字典[7],这种方法应用广泛,易于操作,但是适用性不强,对于任意信号,基于变换的正交基字典无法准确表达信号的可压缩性。因此过冗余的稀疏字典设计引起越来越多的关注,并且通过引入学习算法,克服稀疏字典构造面临的先验知识依赖缺陷,从而构造出与原始信号相适应的优化字典,如应用广泛的最优方向算法(Method of Optimal Directions, MOD)[8]、K-奇异值分解(K-Singular Value Decomposition,K-SVD)[9]等。

测量矩阵的构造效果直接影响到压缩采样后获取的信息量,因此矩阵的构造理论是压缩感知理论形成的一大瓶颈,Candes等[10]在对线性编码系统的系统特性描述中提出:有限等距常数(Restricted Isometry Constant, RIC)在满足特定条件下,重构信号具有唯一性与准确性,随后,Candes[11]针对压缩感知理论提出测量矩阵的有限等距特性(Restricted Isometry Property, RIP)。RIP作为测量矩阵构造的必要条件得到了广泛认可与发展。以此为基础,测量矩阵的构造原则不断丰富,但在本质上保持着一致性,针对不同的编码、构造方式,满足的不同条件,都能在一定程度上保证原始信号的唯一精确重构。

经过压缩采样的信号保留了原始信号重构的必要信息,但信号的重构仍然是一个NP难问题。重构过程利用了原始信号的稀疏特性,在变换域内信号的非零系数有限,这就为信号重构提供了可能。解决这类问题的算法主要包括贪婪算法、凸优化算法等。贪婪算法包括匹配追踪[12]、正交匹配追踪[13]、压缩采样匹配追踪[14]等,这类算法运算速度较快,但是运算精度有限。凸优化算法包括基追踪算法[15]、梯度投影法[16]、内点迭代法[17]等。该类算法运算时间较长,但重构精度较高,适用于原始信号的重构精度要求较高的情况。

在压缩感知理论中,测量矩阵作为原始信号的压缩采样系统,发挥了关键的作用,因此引起国内外学者的广泛关注,测量矩阵大致可以分成随机矩阵以及确定性矩阵。在压缩感知理论之初,服从特定分布的随机矩阵作为测量矩阵,取得了很好的重构效果[5],随后,贝努力随机矩阵[2]、托普利兹测量矩阵[13]以及基于特定编码[6]的确定性矩阵等被证明也能够用于压缩感知的测量矩阵。发展至今,各种矩阵构造方式多样并不断发展,因此本文在总结国内外测量矩阵研究现状的前提下,对压缩感知中测量矩阵构造进行了探讨与研究。

1 压缩感知理论模型

假定离散信号x∈RN,长度为N,把x看作N维列向量,向量中第n个元素可以表示为:xn(n=1,2,…,N),给定一组正交基Ψ={Ψ1,Ψ2,…,ΨN},Ψi为N维列向量,则x可以表示为:

(1)

其中s是由权重系数si组成的N维向量,si可以表示为:

si=〈x,Ψi〉=ΨiTx

(2)

其中T表示转置运算。x与s是信号在时域以及Ψ域内的不同表现方式,因此二者从本质上是等价的。假设信号在Ψ域为K-稀疏信号,则s向量中非零元素的个数为K≪N(远小于),x可以看作是K个基向量的线性组合。若s中只有K个数值较大的权重系数,N-K个系数数值较小或近似于零时,信号在Ψ域可以看作为近似K-稀疏信号,满足上述条件的信号均视为可压缩信号。

y=Φx=ΦΨs=Θs

(3)

其中感知因子Θ=ΦΨ。当原始信号为时域稀疏信号时,变换域可以看作是单位阵,此时,压缩感知因子与测量矩阵相同,由于M≪N,因此从y中直接恢复x的数学模型中,未知量远大于方程个数,求解过程表现为病态,但是由于信号具有可压缩性,即s为K-稀疏信号,这就为y恢复s提供了可能,因此可以通过感知因子求解信号的稀疏系数向量s,在已知原始信号稀疏域的条件下,原始信号就能够得到精确重构。压缩感知理论避免了传统方法先采样、后压缩的复杂过程,基于压缩感知理论的信号获取与传输方法中如图1所示,通过观测矩阵实现了传统方法中采样与压缩两个过程,因此能够有效利用资源,提高信号获取与传输的效率。

图1 信号获取与传输

信号获取过程是测量矩阵压缩观测的过程,信号获取的效果决定了信号能否被精确重构,因此构造合理的测量矩阵是信号能够精确恢复的关键。针对测量矩阵的构造过程,本文将从以下四个方面进行阐述:测量矩阵构造原则、测量矩阵产生方法、测量矩阵结构设计和测量矩阵优化方法。

2 测量矩阵构造原则

对于可压缩信号x,在Ψ域内的K-稀疏信号为s,但s中非零元素的位置信息是未知的。感知因子Θ能够保留稀疏信号s中的足够信息,满足信号重构的要求。对于稀疏性能已知的可压缩信号,变换域Ψ已知,因此测量矩阵的设计直接影响稀疏信号的感知效果,为进一步简化问题,假设可压缩信号x为稀疏信号,因此变换域Ψ为单位阵I,感知因子Θ=ΦΨ=Φ,则压缩感知过程如图2所示。

图2 压缩感知测量过程

压缩采样后得到了M维向量y,测量矩阵构造原则通过对测量矩阵Φ进行约束,保证了原始信号x压缩采样后,依然能够从降维信号y中得到准确的恢复,例如高斯随机矩阵,在K≤O(MlogN)的条件下,能够以很高的概率满足RIP[18],RIP是测量矩阵构造原则中的一种。图3为不同条件下测量矩阵对稀疏信号的压缩感知效果,图3中原始信号为稀疏信号,仿真电压信号在时域的变化趋势,观测矩阵为高斯随机矩阵。当观测采样后信号数据量由1 024减低到512时,测量矩阵能够满足RIP,信号重构后标准差为2.75×10-13,如图3(c);当压缩采样后信号数量由1 024降低到120时,测量矩阵不满足RIP,信号重构标准差为1.18,重构信号严重失真,如图3(b)。因此RIP能够约束测量矩阵,保证原始信号的精确重构,除了RIP之外,学者们对测量矩阵构造原则的研究不断深入,矩阵的构造原则不断丰富,包括RIP1、列相干性等。

图3 稀疏信号压缩感知

2.1 RIP

2.1.1RIC

对于可压缩信号,Armin等[19]给出RIC的定义,若信号为时域稀疏信号,则RIC定义如下。

定义1 对于任意K=1,2,…,定义矩阵Φ的RICδK为满足式(4)的最小值:

(4)

其中x为任意K-稀疏信号。

当信号在时域不具有稀疏性时,需要找到信号的稀疏域,假设信号为Ψ域稀疏信号,则δK定义如下。

定义2 对于任意任意Ψ域K-稀疏信号,K=1,2,…,定义压缩感知因子Θ的RICδK为满足式(5)的最小值:

(5)

对于时域K-稀疏信号,通常情况下x中非零元素位置未知,要精确重构原始信号,需定义δ2K如下。

定义3 对任意索引子集T⊂{1,2,…,N},|T|≤2K,ΦT根据Φ中T所指示的相关列收缩获得,c={xj∣j∈T},则δ2K为满足式(6)的最小值:

(6)

若信号为Ψ域稀疏信号,则δ2K定义与之相类似,但ΦT不能够直接测量非稀疏信号,因此δ2K为满足式(7)的最小值:

(7)

2.1.2RIP的条件描述

RIP通过限制观测矩阵,保证了不同信号在压缩观测后能够映射到不同的集合,同时充分保留原始信号的特性,因此能够保证原始信号的唯一精确重构。RIP的提出,是压缩感知理论上的重要突破:一方面在满足RIP的条件下,远低于奈奎斯特采样定理的信号采样存在精确重构的可能,为压缩感知理论提供基础;另一方面,RIP能够指导测量矩阵的构造,成为部分矩阵构造是否合理的评判标准。文献[20]通过Johnson-Lindenstrauss引理[21]证明,许多密集随机矩阵都能够满足RIP,保证了压缩感知重构效果。

2.2 RIP1性质

满足RIP条件的密集随机矩阵能够满足信号重构的需求,但是在测量以及重构过程中,时间复杂度较高,例如基于l1范数的凸优化重构算法,重构时间复杂度为O(n3),测量个数为O(Klog(N/K))。当原始信号个数N较大时,测量与重构的过程的实现变得十分困难,为此学者提出构造二进制稀疏的测量矩阵,例如离散chirps[16]、边膨胀图[22]等,能够在有限测量次数以及重构时间复杂度的条件下精确重构原始信号。但是在RIP的理论框架下,证明矩阵是否满足RIP显得十分困难,为此学者们提出RIP1[23]以及统计有限等距特性(StatisticRestrictedIsometryProperty,StRIP)和保证唯一性的统计有限等距特性(Uniqueness-guaranteedStatisticRestrictedIsometryProperty,UStRIP)[24]等。

基于边膨胀图的测量矩阵构造方法被提出之后,Berinde等[23]证明了边膨胀图具有与RIP相类似的RIP1性质。满足RIP条件的测量矩阵通过限制压缩采样信号与原始信号的欧几里得距离,保留了原始信号的有用信息,文献[23]将l2范数延伸至l1范数,定义了RIP1性质,并指出边膨胀图通过限制采样信号与原始信号的曼哈顿距离,能够保留原始信号中的有用信息。

定义4 RIP1性质[25]。设Φ为边膨胀图V(K,ε)的M×N邻接矩阵,那么对于任意K-稀疏信号x∈RN,满足:

(1-2ε)d‖x‖1≤‖Φx‖1≤d‖x‖1

(8)

其中:d为Φ每列中1的个数,ε为常数。

RIP1性质是RIP的扩展,二者在本质上保持着一致性。RIP1通过扩展欧几里得空间至曼哈顿空间,丰富了RIP的应用范围,建立了膨胀图与压缩感知之间的联系,为边膨胀图的确定性矩阵构造方式提供依据。同时,进一步揭示了RIP的实质,即通过保证压缩观测过程保留原始信号在欧几里得空间的基本特性,保证原始信号具有精确重构的可能。

2.3 列相干性

为避免RIP的复杂求解过程,Donoho等[26]从压缩采样后信号的精确重构条件出发,提出利用列相干性优化测量矩阵设计。

Tropp[27]提出,在冗余字典满足特定列相干性条件的情况下,基追踪(BasisPursuit,BP)、正交匹配追踪(OrthogonalMatchingPursuit,OMP)等追踪算法能够对原始信号实现准确的稀疏近似。在此基础上,Donoho等[26]将这一结论应用到压缩感知矩阵优化中,作为测量矩阵优化标准,提出了基于列相干性的测量矩阵构造原则。

定义5 对于任意字典Ψ,其互相干系数定义为μ以及累积互相干系数μ1定义为:

(9)

定理1 对于一般字典而言,其相干系数有下界:

(10)

若字典中所有原子都满足等式条件,那么字典叫作等角紧框架。

对于可压缩信号x,其在稀疏字典下的系数表示为:

x=ψs

(11)

若测量矩阵为Φ,则Θ=ΦΨ,列相干性条件通过感知因子的列相干系数定义,若满足:

(12)

则矩阵Θ满足列相干性条件。

相对于RIP,列相干性条件更为简单,计算量相对较小,Rauhut等[28]证明,二者之间存在必然联系,定理2对二者的关系进行了描述,可以证明:在满足列相干性条件的情况下,感知因子满足RIP。

定理2 若字典互相干系数为μ以及累积互相干系数为μ1,则RICδK满足下列约束:

δK≤μ1(K-1)≤(K-1)·μ

(13)

列相干性从信号重构的角度,提出了在压缩采样过程,感知因子需要满足的性质。式(13)反映出列相干性与RIP之间的关系,列相干性条件通过限制感知因子不同列向量之间的相互关联性,保证了感知因子能够从各个维度对原始信号完成压缩感知,因此能够保证压缩观测的效果,为信号的精确重构保留足够的信息量。

2.4 StRIP/UStRIP性质

针对RIC以及RIP的计算困难问题,Calderbank等提出统计有限等距特性(StRIP)以及保证唯一性的统计有限等距特性(UStRIP)[24],同时,提出StRIP/UStRIP的简单评判标准,通过判断测量矩阵是否满足特定标准,来确定测量矩阵是否满足StRIP/UStRIP性质,具有较强的可行性。

定义6Φ为M×N测量矩阵,对于任意K-稀疏信号x∈RN,若下列不等式能够以超过1-δ的概率成立:

(1-ε)‖x‖2≤‖Φx/M‖2≤(1+ε)‖x‖2

(14)

则Φ为(K,ε,δ)-StRIP矩阵。

满足上述条件的StRIP矩阵并不能保证满足重构信号的唯一性要求,因此定义严格约束的UStRIP矩阵。

定义7M×N阶测量矩阵Φ为(K,ε,δ)-StRIP矩阵,若下列等式(15)能够以超过1-δ的概率成立:

(15)

则Φ为(K,ε,δ)-UStRIP矩阵。

以上给出StRIP/UStRIP性质的定义,但是在判断矩阵是否满足上述性质过程中,仍然存在一定困难,为此给出η-StRIP-able矩阵的评判标准定义。

定义8 定义η-StRIP-able矩阵,0<η<1,为满足以下标准的Φ矩阵。

1)Φ任意行向量正交,并且行元素求和为零。即:

(16)

(17)

其中:j为列索引,a、b为行索引。

2)Φ的任意列向量满足“逐点相乘”,即对于任意列向量Φj″(a)(j″∈{1,2,…,N}),存在不同的列索引j,j′,对任意x满足:

Φj″(a)=Φj′(a)Φj(a)

(18)

3)对任意j∈{2,…,N}满足:

(19)

文献[24]证明,满足标准1)~3)的测量矩阵,具有统计意义上的有限等距性质,即具有StRIP/UStRIP性质。η-StRIP-able矩阵可行性强,成为许多二进制稀疏编码测量矩阵的评价指标,例如离散Chirp编码[16]、Bose-Chaudhuri-Hocquenghem编码[24]等。

StRIP/UStRIP性质通过缩小测量矩阵的应用对象,简化了测量矩阵的评价条件,降低了测量矩阵性质的检验难度。对于满足条件的稀疏信号而言,简单的评价条件具有与RIP类似的性质,能够保证测量矩阵在压缩观测过程中充分保留原始信号的有用信息,从而保证原始信号的唯一精确重构。

除此之外,测量矩阵构造原则还包括Spark理论[29]、零空间理论[30]等,Spark理论与列相干性理论相类似,利用矩阵的最小线性相关向量组的数目作为Spark常数,判断是否满足矩阵构造条件。零空间理论通过判断稀疏信号是否在感知因子的零空间内,判断解的唯一性。

3 测量矩阵产生方法

自压缩感知理论产生以来,压缩感知测量矩阵的构造方法不断丰富,产生的矩阵大致可以分成随机测量矩阵、确定性测量矩阵两大类。

3.1 随机测量矩阵

3.1.1 高斯随机矩阵

Candes等[2]证明,独立同分布于高斯正态分布的高斯矩阵,在K≤O(MlogN)的条件下,能够以很高的概率满足RIP[18],因此作为测量矩阵对K-稀疏信号进行压缩采样后,能够以很高的概率实现原始信号的精确重构。

高斯随机矩阵中,每个元素独立同分布且均值为0、方差为1/n的正态分布,即:

Φi, j~N(0,1/M)

(20)

其中i、j表示矩阵的第i行、第j列。

3.1.2 贝努力随机矩阵

与高斯矩阵性类似,独立同分布的贝努力随机矩阵能够以很高的概率满足RIP。贝努力矩阵为二值随机矩阵,两取值的概率相等,均为1/2,其元素取值可以描述为如下形式:

(21)

文献[31]丰富了贝努力随机矩阵的构造方法,提出了通过部分哈达玛集合、二进制集合以及二者相组合的方式构造贝努力随机矩阵,并证明了这些方式能够以超过1-2exp(-c1M)的概率满足RIP。

与高斯随机矩阵相比,贝努力随机矩阵保留了高斯矩阵随机性以及独立性,能够在相同的测量次数下满足RIP,同时,贝努力随机矩阵的数值变化少,结构相对简单。

除此之外,随机矩阵还包括部分傅里叶矩阵[32]、部分正交矩阵[2]、稀疏随机矩阵[33]等。这些随机矩阵的独立性较好,在一定程度上具有RIP,但是由于其随机性,矩阵的硬件实现较为复杂,因此学者们研究确定性矩阵的构造算法[34],通过确定性矩阵来实现原始信号的压缩观测过程。

3.2 确定性测量矩阵

3.2.1 边膨胀图邻接矩阵

Xu等[22]提出利用非平衡二部图(如图4)邻接矩阵作为测量矩阵,应用于压缩观测过程。非平衡二部图直接模拟了压缩感知压缩观测过程,其图形分为左右两部分,左子图定义为A1,右子图定义为A2,图中包含有两种节点。根据编码理论的数值描述,将A1中节点定义为可变节点,A2中节点定义为奇偶校验节点。A1节点个数为N,对应于压缩感知原始信号x;A2节点个数为M,对应于压缩观测后信号y。假设M≤N,A1、A2节点之间有边线连接,连接关系对应于邻接矩阵C:

(22)

其中:i=1,2,…,M;j=1,2,…,N。

图4 (k,ε)-边膨胀图

定理3 定义C(K,ε)-边膨胀图为形如图4的非平衡二部图V(A1,A2),|A1|=N,|A2|=M,A1为可变节点,A2为奇偶检验节点。假设A1的度为d,对于任意S⊂A1,若|S|≤K,则邻居节点数N(S)满足:N(S)>(1-ε)|S|。

Jarfarpour等[25]指出,在1≤K≤N/2的情况下,若(K,ε)-边膨胀图存在左子图的度d以及右子图大小M为:

(23)

则其邻接矩阵C,对任意K-稀疏信号满足RIP1性质。

3.2.2 多项式确定性矩阵

基于压缩感知理论,Devore[35]提出利用多项式映射矩阵构造确定性矩阵,多项式确定性矩阵利用了有限域的理论。假设素数p,有限域F内的元素为p的整数模,因此有限域F的阶为p,即F域内有p个元素,F可以表示为:{0,1,…,p-1}。构建p×p矩阵E,因此E中含有p2个元素,E中元素的赋值方式如下。

定义整数r(0

(24)

Pr中多项式的个数为pr+1,对于任意Q∈Pr,把Q当作F→F的映射函数,则E为t→Q(t)的映射矩阵,满足:

Q(t)=Et*

(25)

式中t*表示t所有取值的集合。

将矩阵E的位置索引定义为:

(26)

则E中索引为(t,Q(t))位置处元素为1,其他位置为零,将E变换成p2×1的向量vQ,vQ中每p个元素中包含一个1,总共有p个1,多项式系数取值不同,产生不同的向量,因此当系数取完时,可以构造出pr+1个向量,将每一个的向量作为一列,构造一个p2×pr+1的矩阵。

Devore[35]证明,按照上述方式构造的确定性矩阵在稀疏信号稀疏度K

3.2.3 编码矩阵

受有限域思想的启发,学者们扩展现有编码方式的应用领域,构造用于压缩观测的测量矩阵。

Nam等[36]提出利用正交光码(OpticalOrthogonalCode,OOC)构造压缩感知确定性矩阵,光正交码的构造由Brickell等[37]提出,广泛应用在光线信道的码分多址信道设计,Nam等[36]通过OOC的循环位移以及哈达玛矩阵的嵌套,构造了一个三元实数矩阵,并证明了其优越性能,OOC定义如下。

定义9 (n,ω,λ)光正交码(OOC)为一组元素个数为n的二元序列,如{v(i)∣0≤i≤n-1}。每一序列的非零元素个数为ω,两序列之间,满足:

∀τ∈[0,n-1],θv(i),v(j)(τ)≤λ;τ=0,若i=j

(27)

(28)

其中⊕表示模n加。

光正交码的构造利用了循环差集组G,G(n,ω)为ω个非零模n整数,任意两个整数之间的差值互异。定义特征序列a={at∣t∈(0,1,…,n-1)},若t∈G,则at=1,否则at=0,则a∈(n,ω,1)OOC。

在OOC码的基础上,测量矩阵的构造方式如下:

1)生成S个0-1序列v(i)(0≤i≤n-1),属于(n,ω,λ)OOC码,将每一序列v(i)进行循环位移,共产生nS个序列,每一序列作为矩阵B的列向量。

2)构造v×v(v=ω+δ,0≤δ≤ω)哈达玛矩阵H,对于B的每一列,将元素1用H中不同的行替换,将元素0扩展成长度为v的行,元素均为0,生成n×vnS矩阵Be。

除此之外,Bose-Chaudhuri-Hocquenghem编码[38]、离散Chirp编码[16]、代数编码[39]、Reed-Muller编码[24]、Berlekamp-Justesen编码[40]以及各种低密度奇偶校验码(Low-DensityParity-Check,LDPC)编码[41]等,均被证明能够作为压缩感知测量矩阵,实现原始信号的精确重构。

4 测量矩阵结构设计

随着压缩感知测量矩阵构造算法的不断丰富,学者们提出通过优化测量矩阵结构设计的方法,综合不同算法的优势,构造更为合理的测量矩阵。Do等[42]提出的结构随机矩阵,通过随机置换不同的列或将元素的位置索引进行翻转,构造一种正交矩阵,能够保留原有高斯随机矩阵以及贝努力随机矩阵的所有优势。常用的测量矩阵的结构设计方式主要包括托普利兹轮换矩阵、分块矩阵、嵌套矩阵。

4.1 托普利兹轮换矩阵

托普利兹矩阵通过向量轮换的方式构造矩阵[43],这种方式的结构化特点明显,因此易于硬件实现,与独立同分布的随机矩阵相比,生成随机变量数目少,运算复杂度低,重构算法相对简单,因此轮换的矩阵构造形式引起广泛关注。在构造过程中首先生成元素为±1贝努力分布的向量g=(g1,g2,…,gn),并作为托普利兹矩阵的第一行向量,然后通过轮换的方式构造矩阵其他行向量,最后按列进行归一化处理,归一化后元素定义为u,矩阵如式(29)所示:

(29)

Bajwa等[44]提出,当矩阵中元素独立服从特定P(u),且M≥K3ln(N/K)时,存在3K阶RICδ3K∈(0,1/3),满足RIP。

托普利兹矩阵可以与特定序列相结合,生成具有托普利兹结构的特定序列矩阵,如离散Chirps托普利兹矩阵[44]等。

4.2 分块矩阵

大量满足RIP的测量矩阵在结构上表现为密集矩阵,这种矩阵在原始信号重构上表现出优异性能,但是在矩阵的构造上,由于其密集性,存在存储困难、计算复杂等问题。为此学者提出了分块矩阵的结构设计方式来克服上述缺陷。

文献[19]提出分块对角的矩阵结构设计,采用亚高斯的随机矩阵构造方法,实现对稀疏信号的压缩观测,其模型可以描述为:

(30)

其中测量矩阵Φ为M×N矩阵。若式中每个矩阵块Φj元素不同,则称为不同块对角矩阵(DistinctBlockDiagonal,DBD),若相同则称为重复块对角矩阵(RepeatBlockDiagonal,RBD)。Armin等[19]指出,二者在保证测量次数的条件下,均能够满足RIP,实现与高密度亚高斯随机矩阵几乎相同的测量效果。

除此之外,分块的矩阵结构与循环、稀疏矩阵融合,产生分块循环矩阵[46]、稀疏分块循环矩阵[47]等,在一定程度上都能满足RIP。

4.3 嵌套矩阵

列相干性是衡量测量矩阵性能的重要指标,对于一些二元矩阵而言,由于元素具有非负性,因此低相干性的矩阵构造显得十分困难,这也使得矩阵维度受到极大限制。Amini等[38]从矩阵结构角度提出了嵌套矩阵的构造方法,能够在保证矩阵列相干性的条件下扩展矩阵维度,从而使得确定性矩阵的构造方式更加灵活。

定理4 假设二元矩阵VM×N1,矩阵V中每一列具有相同的非零元素,元素个数为p,列相干系数为μ(V),矩阵W为p×N2,矩阵中所有元素的绝对值相同,则可以构造一个嵌套矩阵ZM×(N1N2),列相干性系数满足μ(Z)≤max(μ(V),μ(W))。

矩阵构造过程如图5所示,矩阵V中的第i个非零元素用矩阵W中的第i行代替,零元素延伸至相同维度,直至矩阵中非零元素替换完毕。

图5 嵌套矩阵

根据定理4,通过嵌套列相干系数小的矩阵,可以实现在列相干系数不变的条件下扩展矩阵维度,如嵌套哈达玛矩阵[36]、离散傅里叶变换矩阵[48]等。

5 测量矩阵优化方法

无论是确定性观测矩阵还是随机矩阵,由于受限于矩阵的构造方式,观测矩阵构造完成后不再发生改变,但大部分矩阵仍然有很大的优化空间,为此学者们从测量矩阵的性能出发,提出了对测量矩阵进行优化的方法,来进一步改善压缩观测的效果。

5.1 基于Gram的优化算法

Elad[49]提出把压缩感知因子Θ的互相干系数作为目标函数,通过构造Gram矩阵以及阈值缩放处理方法降低测量矩阵Φ与稀疏域Ψ的相干性。根据互相干系数的定义,压缩感知因子互相干系数为:

(31)

其中Θ经过单位化处理,Θi为Θ的第i行,定义Gram矩阵Ξ为:

Ξ=ΘTΘ

(32)

感知因子的互相干系数的最大值为矩阵Ξ非对角位置元素的最大值,定义Ξ元素为Ξij,则μmax(Θ)=max(Ξij)(i≠j)。因此优化过程中,根据预设阈值与矩阵Ξ中元素的大小关系,来对矩阵Ξ重新进行赋值,已达到降低互相干系数的目的,整个优化过程通过迭代次数控制,每次迭代过程中元素赋值方法为:

(33)

经过优化后,感知因子的互相干系数变小,测量矩阵与稀疏域的相关性减弱,文献[49]表明,采用Elad优化算法优化的测量矩阵,在压缩采样后,重构信号的精度得到提高。

Elad算法改善了测量矩阵压缩采样效果,但是其复杂度较高,为此在矩阵Ξ的基础上,学者们进一步优化了目标函数[50]。

对于满足式(32)的矩阵Ξ,在压缩感知因子的互相干性系数为0的理想状态下,Ξ为单位阵:

Ξ=ΨTΦTΦΨ=I

(34)

对式(34)进行变换得到:

ΨΨTΦTΦΨΨT=ΨΨT

(35)

(36)

式(36)通过改进目标函数,测量矩阵的优化复杂度得到明显降低,优化求解的效率得到有效提高。

除此之外,基于Gram矩阵的优化方法还包括交互投影法[51]、特征值分解[52]等。不同的优化方法都是通过降低Gram矩阵非对角元素的大小,降低测量矩阵与稀疏域的相干性,从而保证感知因子具有较小的互相干系数,改善压缩感知效果。

5.2 联合优化算法

基于Gram矩阵的优化算法假设信号的稀疏变换域为固定的正交基字典,但是随着自适应稀疏算法的产生,信号的稀疏域更多地转向自适应冗余字典。为此测量矩阵与稀疏字典联合优化的方法得到越来越多的关注,文献[53]基于K-SVD算法,提出了稀疏字典-测量矩阵联合优化的算法,并应用在图像压缩领域,取得了更高的重构精度。

联合优化算法具体步骤为:

1)初始化稀疏字典Ψ。

2)固定稀疏字典Ψ,采用基于Gram矩阵的优化方法,初始化测量矩阵Φ。

3)固定感知因子Θ,利用OMP算法求得稀疏分解系数矩阵。

4)利用K-SVD算法实现稀疏字典Ψ与测量矩阵Φ的迭代更新,直至满足迭代条件。

除此之外,联合优化算法还包括基于梯度下降的联合优化[54]、基于奇异值分解的联合优化[55]等。联合优化算法引用了自适应稀疏字典的学习训练过程,通过不断的迭代,构建了一个与原始信号相适应的稀疏字典以及观测矩阵,因此压缩感知效果得到改善,但是相比非联合优化算法而言,算法复杂度提高,优化时间消耗增加。

6 测量矩阵构造发展方向探讨

测量矩阵构造为基于压缩感知理论的信号采集与传输提供了支撑,然而目前测量矩阵构造方式并不完善,仍然有一些问题需要在今后的研究中取得突破,为此在总结国内外现有研究成果的前提下,对测量矩阵设计的发展方向进行展望:

1)在测量矩阵构造原则上,RIP是测量矩阵设计的必要条件,但是无法有效指导测量矩阵构造,列相干性条件与RIP存在一致性,其计算简单、指导性强,并且基于列相干性条件的矩阵训练方法被证明能够用来优化测量矩阵,因此列相干性条件在具体指导测量矩阵构造中将发挥越来越大的作用;另一方面J-R引理在证明矩阵RIP上体现出巨大优势,因此其作为评价矩阵优劣的简单途径,将得到广泛应用。

2)在测量矩阵产生方法上,确定性矩阵无疑将成为研究热点,现有确定性矩阵在部分信号的重构精度以及普遍适用性上与随机矩阵稍显不足,但是其构造复杂度低、硬件实现简单,已经得到学者的广泛关注,因此在保证重构精度的基础上,更加适用、简单的确定性矩阵是测量矩阵产生方法的发展趋势。

3)测量矩阵结构设计能够弥补不同测量矩阵产生方法的不足,从而起到优化测量矩阵的作用,现阶段,矩阵结构设计方法相对较少,理论基础相对薄弱,因此针对测量矩阵的结构设计方法有待于进一步完善,相应的理论有待于进一步研究。

4)对于按照特定方式构造的测量矩阵,矩阵优化方法是对其性能的一种完善,能够进一步改善测量矩阵压缩观测效果。随着自适应稀疏分解算法的不断成熟,测量矩阵与稀疏字典联合优化的方法将得到越来越多的重视,并逐渐体现出单一测量矩阵优化所不具有的优化效果。但由于现有联合优化算法的复杂度较高,联合优化算法仍处于理论研究阶段,因此未来高效率的联合优化算法将成为学者们的研究热点。

7 结语

压缩感知测量矩阵设计是压缩感知理论框架的核心,本文在对国内外学者众多文献梳理研究的前提下,对测量矩阵构造进行系统介绍,分析现有研究成果,从测量矩阵构造原则、测量矩阵产生方法、测量矩阵结构设计、测量矩阵优化方法等角度比较不同方法、理论的优缺点,为后续压缩感知测量矩阵构造提供了参考。现阶段,低复杂度的测量矩阵构造方式、测量矩阵的优化方法大多处于理论研究阶段,在实际应用过程中压缩感知效果、适用性有待于进一步检验与提高。此外,本文着重对测量矩阵的构造进行了介绍,而压缩感知效果是稀疏字典、测量矩阵、重构算法共同作用的结果,因此构建与稀疏字典、重构算法相适应的测量矩阵有待于进一步研究。

)

[1]CANDESEJ,ROMBERGJ.Quantitativerobustuncertaintyprinciplesandoptimallysparsedecompositions[J].FoundationofComputationalMathematics, 2006, 6(2): 227-254.

[2]CANDESEJ,ROMBERGJK,TAOT.Robustuncertaintyprinciples:exactsignalreconstructionfromhighincompletefrequencyinformation[J].IEEETransactionsonInformationTheory, 2006, 52(2): 489-509.

[3]CANDESEJ,ROMBERGJK,TAOT.Stablesignalrecoveryfromincompleteandinaccuratemeasurements[J].CommunicationsonPureandAppliedMathematics, 2006, 59(8): 1207-1223.

[4]BOUCHHIMAB,AMARAR,ALOUANETH.Designofoptimalmatricesforcompressivesensing:applicationtoenvironmentalsounds[C]//Proceedingsofthe2015SignalProcessingConference.Piscataway,NJ:IEEE, 2015: 130-134.

[5]DONOHODL.Compressedsensing[J].IEEETransactionsonInformationTheory, 2006, 52(4): 1289-1306.

[6] 王强,李佳,沈毅.压缩感知中确定性测量矩阵构造算法综述[J].电子学报,2013,41(10):2041-2050.(WANGQ,LIJ,SHENY.Asurveyondeterministicmeasurementmatrixconstructionalgorithmsincompressivesensing[J].ActaElectronicaSinica, 2013, 41(10): 2041-2050.)

[7] 焦李成,杨淑媛,刘芳,等.压缩感知回顾与展望[J].电子学报,2011,39(7):1651-1662.(JIAOLC,YANGSY,LIUF,etal.Developmentandprospectofcompressivesensing[J].ActaElectronicaSinica, 2011, 39(7): 1651-1662.)

[8]ELADM,AHARONM.Imagedenoisingviasparseandredundantrepresentationsoverlearneddictionaries[J].IEEETransactionsonInformationTheory, 2006, 15(12): 3736-3745.

[9]AHARONM,ELADM,BRUCKSTEINAM.TheK-SVD: an algorithm for designing of overcomplete dictionaries for sparse representations [J].IEEE Transactions on Image Processing, 2006, 54(11): 4311-4322.

[10] CANDES E J, TAO T.Decoding by linear programming [J].IEEE Transactions on Information Theory, 2005, 51(12): 4203-4215.

[11] CANDES E J.The restricted isometry property and its implication for compressed sensing [J].Comtes Rendus Mathematique, 2008, 346(9/10): 589-592.

[12] MALLAT S, ZHANG Z F.Matching pursuits with time frequency dictionaries [J].IEEE Transactions on Signal Processing, 1993, 41(12): 3397-3415.

[13] TROPP J A, GILBERT A C.Signal recovery from random measurement via orthogonal matching pursuit [J].IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666.

[14] NEEDELL D, TROPP J A.CoSaMP: iterative signal recovery from incomplete and inaccurate samples [J].Applied and Computational Harmonic Analysis, 2008, 26(3): 301-321.

[15] CHEN S B, DONOHO D L, SAUNDERS M A.Atomic decomposition by basis pursuit [J].SIAM Journal on Scientific Computing, 1998, 20(1): 33-61.

[16] APPLEBAUM L, HOWARD S, SEARLE S, et al.Chirp sensing codes: deterministic compressed sensing measurements for fast recovery [J].Applied and Computational Harmonic Analysis, 2009, 26(2): 283-290.

[17] ROMBERG J.Compressive sensing by random convolution [J].SIAM Journal on Imaging Sciences, 2009, 2(4): 1098-1128.

[18] CANDES E J, TAO T.Near-optimal signal recovery from random projections: universal encoding strategies? [J].IEEE Transactions on Information Theory, 2006, 52(12): 5406-5425.

[19] ARMIN E, LUN Y H, CHRISTOPHER J R, et al.The restricted isometry property for random block diagonal matrices [J].Applied & Computational Harmonic Analysis, 2015, 38(1): 1-31.

[20] BARANIUK R, DAVENPORT M, DEVORE R, et al.A simple proof of the restricted isometry property for random matrices [J].Constructive Approximation, 2008, 28(3): 253-263.

[21] JOHNSON W, LINDENSTRAUSS J.Extensions of Lipschitz maps into a Hilbert space [J].Contemporary Mathematics, 1984, 26: 189-206.

[22] XU W, HASSIBI B.Efficient compressive sensing with deterministic guarantees using expander graphs [C]// ITW’07: Proceedings of the 2007 Information Theory Workshop.Piscataway, NJ: IEEE, 2007: 414-419.

[23] BERINDE R, GILBERT A C, INDYK P, et al.Combining geometry and combinatorics: a unified approach to sparse signal [EB/OL].[2016-05-15].https://arxiv.org/abs/0804.4666.

[24] CALDERBANK R, HOWARD S, JAFARPOUR S.Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property [J].IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 358-374.

[25] RAGINSKY M, JAFARPOUR S, HARMANY Z T, et al.Performance bounds for expander-based compressed sensing in Poisson noise [J].IEEE Transactions on Signal Processing, 2011, 59(9): 4139-4153.

[26] DONOHO D L, ELAD M.Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization [J].Proceedings of the National Academy of Sciences, 2003, 100(5): 2197-2202.

[27] TROPP J A.Greed is good: algorithmic results for sparse approximation [J].IEEE Transactions on Information Theory, 2004, 50(10): 2231-2242.

[28] RAUHUT H, SCHNASS K, VANDERGHEYNST P.Compressed sensing and redundant dictionaries [J].IEEE Transactions on Information Theory, 2008, 54(5): 2210-2219.

[29] ELAD M, BRUCKSTEIN A M.A generalized uncertainty principle and sparse representation in pairs bases [J].IEEE Transactions on Information Theory, 2002, 48(9): 2558-2567.

[30] KASHIN B S, TEMLYAKOV V N.A remark on compressed sensing [J].Mathematics and Statistics, 2007, 42(5/6): 748-755.

[31] ZHANG G, JIAO S, XU X, et al.Compressed sensing and reconstruction with Bernoulli matrices [C]// Proceedings of the 2010 International Conference on Information and Automation.Piscataway, NJ: IEEE, 2010: 455-460

[32] GILBERT A C, GUHA S, INDYK P.Near-optimal sparse Fourier representation via sampling [C]// Proceedings on the 34th Annual ACM Symposium on Theory of Computing.New York: ACM, 2006: 152-161.

[33] BERINDE R, INDYK P.Sparse recovery using sparse random matrices [C]// LATIN 2010: Proceedings of the 9th Latin American Symposium on Theoretical Informatics, LNCS 6034.Berlin: Springer, 2010: 157-157.

[34] ZENG L, ZHANG X, CHEN L, et al.Deterministic construction of Toeplitzed structurally chaotic matrix for compressed sensing [J].Circuits, Systems, and Signal Processing, 2015, 34(3):797-813.

[35] DEVORE R A.Deterministic construction of compressed sensing [J].Journal of Complexity, 2007, 23(4/5/6): 918-925.

[36] NAM Y Y, NA Z.Deterministic construction of real-valued ternary sensing matrices using optical orthogonal codes [J].IEEE Signal Processing Letters, 2013, 20(11): 1106-1109.

[37] BRICKELL E F, WEI V K.Optical orthogonal codes and cyclic block designs [J].Congressus Numerantium, 1987, 58: 175-192.

[38] AMINI A, MONTAZERHODJAT V, MARVASTI F.Matrices with small coherence using parry block codes [J].IEEE Transactions on Signal Processing, 2012, 60(1): 172-181.

[39] LI S X, GAO F, GE G N, et al.Deterministic construction of compressed sensing matrices via algebraic curves [J].IEEE Transactions on Information Theory, 2012, 58(8): 5035-5041.

[40] GE X, XIA S T.LDPC codes based on Berlekamp-Justesen codes with large stopping distances [C]// ITW’06: Proceedings of the 2006 IEEE Information Theory Workshop.Piscataway, NJ: IEEE, 2006: 214-218.

[41] DIMAKIS A G, SMARANDACHE R, VONTOBEL P O.LDPC codes for compressed sensing [J].IEEE Transactions on Information Theory, 2010, 58(5): 3093-3114.

[42] DO T T, TRAN T D, LU G.Fast compressive sampling with structurally random matrices [C]// Proceedings of the 2008 IEEE International Conference on Acoustics.Piscataway, NJ: IEEE, 2008: 3369-3372.

[43] 李浩.用于压缩感知的确定性测量矩阵研究[D].北京:北京交通大学,2011:26-38.(LI H.Research on deterministic measurement matrix for compressed sensing [D].Beijing: Beijing Jiaotong University, 2011: 26-38.)

[44] BAJWA W U, HAUPT J D, RAZ G M, et al.Toeplitz-structured compressed sensing matrices [C]// SSP’ 07: Proceedings of the 2007 IEEE/SP 14th Workshop on Statistical Signal Processing.Washington, DC: IEEE Computer Society, 2007: 294-298.

[45] SALIGRAMA V.Deterministic designs with deterministic guarantees: Toeplitz compressed sensing matrices, sequence design and system ID [J].IEEE Transactions on Information Theory, 2012, 99(PP): 1-1.

[46] SEBERT F, ZOU Y M, YING L.Toeplitz block matrices in compressed sensing and their applications in imagine [C]// Proceedings of the 2008 International Conference on Information Technology and Applications in Biomedicine, Piscataway, NJ: IEEE, 2008: 47-50.

[47] SUN J M, WANG S, DONG Y.Sparse block circulant matrices for compressed sensing [J].IET Communications, 2013, 7(13): 1412-1418.

[48] 夏树涛,刘璐,刘鑫吉.基于Berlekamp-Justesen码的压缩感知确定性测量矩阵的构造[J].电子与信息学报,2015,37(4):763-769.(XIA S T, LIU L, LIU X J.Deterministic constructions of compressive sensing matrices based on Berlekamp-Justesen codes [J].Journal of Electronics & Information Technology, 2015, 37(4): 763-769.

[49] ELAD M.Optimized projections for compressed sensing [J].IEEE Transactions on Signal Processing, 2007, 55(12): 5695-5702.

[50] 张劲东,张弓,潘汇,等.基于滤波器结构的压缩感知雷达感知矩阵优化[J].航空学报,2013,34(4):866-868.(ZHANG J D, ZHANG G, PAN H, et al.Optimized sensing matrix design of filter structure based compressed sensing radar [J].Acta Aeeronautica et Astronautica Sinica, 2013, 34(4): 866-868.)

[51] LI B, SHEN Y, LI J.Dictionaries construction using alternating projection method in compressive sensing [J].IEEE Signal Processing Letters, 2011, 18(11): 662-666.

[52] 赵瑞珍,秦周,胡绍海,等.一种特征值分解的测量矩阵优化方法[J].信号处理,2012,38(5):654-656.(ZHAO R Z, QIN Z, HU S H, et al.An optimization method for measurement matrix based on eigenvalue decomposition [J].Signal Processing, 2012, 38(5): 654-656.)

[53] DUARTE-CARVAJALINO J M, SAPIRO G.Learning to sense sparse signal: simultaneous sensing matrix and sparsifying dictionary optimization [J].IEEE Transactions on Imagine Processing, 2009, 18(7): 1395-1408.

[54] ABOLGHASEMI V, SAIDEH F, BAHADOR M.On optimization of the measurement matrix for compressive sensing [C]// EUSIPCO 2010: Proceedings of the 18th European Signal Processing Conference, 2010:23-27.

[55] ZHANG J D, ZHU D Y, ZHANG G.Adaptive compressed sensing radar oriented towards cognitive detection in dynamic sparse target scene [J].IEEE Transactions on Signal Processing, 2012, 60(4): 1718-1729.

This work is supported by the Natural Science Foundation of China (E51305454).

WANG Qiang, born in 1992, M.S.candidate.His research interests include signal processing, data compression.

ZHANG Peilin, born in 1955, Ph.D., professor.His research interests include machine condition monitoring, fault diagnosis.

WANG Huaiguang, born in 1979, Ph.D., lecturer.His research interests include signal processing, data compression.

YANG Wangcan, born in 1988, Ph.D.candidate.His research interests include fault diagnosis, pattern recognition.

CHEN Yanlong, born in 1987, Ph.D.candidate.His research interests include fault diagnosis, signal processing.

Survey on construction of measurement matrices in compressive sensing

WANG Qiang, ZHANG Peilin*, WANG Huaiguang, YANG Wangcan, CHEN Yanlong

(DepartmentofVehiclesandElectricalEngineering,OrdnanceEngineeringCollege,ShijiazhuangHebei050003,China)

The construction of measurement matrix in compressive sensing varies widely and is on the development constantly.In order to sort out the research results and acquire the development trend of measurement matrix, the process of measurement matrix construction was introduced systematically.Firstly, compared with the traditional signal acquisition theory, the advantages of high resource utilization and small storage space were expounded.Secondly, on the basis of the framework of compressive sensing and focusing on four aspects: the construction principle, the generation method, the structure design of measurement matrix and the optimal method, the construction of measurement matrix in compressive sensing was summarized, and advantages of different principles, generations and structures were introduced in detail.Finally, based on the research results, the development directions of measurement matrix were prospected.

Compressive Sensing (CS); measurement matrix; Restricted Isometry Property (RIP); signal reconstruction; signal acquisition

2016-08-06;

2016-09-06。 基金项目:国家自然科学基金资助项目(E51305454)。

王强(1992—),男,山东栖霞人,硕士研究生,主要研究方向:信号处理、数据压缩; 张培林(1955—),男,安徽太和人,教授,博士,主要研究方向:机械状态监测、故障诊断; 王怀光(1979—),男,河北石家庄人,讲师,博士,主要研究方向:信号处理、数据压缩; 杨望灿(1988—),男,河北辛集人,博士研究生,主要研究方向:故障诊断、模式识别; 陈彦龙(1987—),男,四川资阳人,博士研究生,主要研究方向:故障诊断、信号处理。

1001-9081(2017)01-0188-09

10.11772/j.issn.1001-9081.2017.01.0188

TP301.6

A

猜你喜欢

字典重构定义
“双减”能否重构教育生态?
长城叙事的重构
高盐肥胖心肌重构防治有新策略
字典的由来
大头熊的字典
北京的重构与再造
正版字典
成功的定义
修辞学的重大定义
山的定义