一种适用于TDOMP算法的测量矩阵优化方法

赵 娟白 霞

（北京理工大学信息与电子学院 北京 100081）

一种适用于TDOMP算法的测量矩阵优化方法

赵 娟*白 霞

（北京理工大学信息与电子学院 北京 100081）

测量矩阵的优化设计有利于提高压缩感知中信号的重构性能。该文研究了适用于TDOMP （Two Dictionaries OMP）重构算法的测量矩阵优化方法。TDOMP算法是一种改进的OMP算法，该算法使用与感知矩阵互相关性低的匹配矩阵来辨识正确的感知矩阵原子。所提方法利用交替投影的思想来优化测量矩阵从而得到相关性低的感知矩阵和匹配矩阵，然后用于TDOMP算法来提高信号的重建性能。仿真实验验证了所提方法的有效性。

压缩感知；测量矩阵；Gram矩阵；互相关

引用格式：赵娟， 白霞. 一种适用于TDOMP算法的测量矩阵优化方法［J］. 雷达学报， 2016， 5（1）： 8-15. DOI：10.12000/JR15131.

Reference format： Zhao Juan and Bai Xia. Measurement matrix optimization method for TDOMP algorithm［J］. Journal of Radars， 2016， 5（1）： 8-15. DOI： 10.12000/JR15131.

1 引言

压缩感知（Compressed Sensing， CS）［1-3］是一种新的信号获取与处理的理论框架，其基本思想是利用信号的稀疏性或者可压缩性，在信号采样的同时进行压缩，能以远低于奈奎斯特采样定理所需的测量值精确重建原始信号，广泛应用于雷达、通信、核磁成像等领域［4-6］。

压缩感知理论包括3个方面：信号的稀疏表征、测量矩阵的设计以及重构算法。假设信号在某个基下能稀疏表征，即x=Ψs，其中是稀疏表征矩阵，s中只有k个非零元素，且k＜＜n。设计测量矩阵对信号x进行线性测量，得到y=Φx，其中） 为测量矩阵。由于m＜n，由y重建x是病态问题。利用信号x的稀疏性，可以通过求解l0范数最小化问题来恢复原始信号，即其中l0范数表示向量中的非零元素的个数，矩阵称为感知矩阵。对于重构算法，主要有基于凸优化的l1范数最小化算法（比如基追踪算法（Basis Pursuit， BP）［7］）和贪婪类算法（比如正交匹配追踪算法（Orthogonal Matching Pursuit，OMP）［8］）等。

信号能够稀疏表征是应用压缩感知的前提，而测量矩阵的设计对信号采样和重构环节有重要影响。测量矩阵把信号从高维空间投影到低维空间，必须保证降维后的低维信号不丢失原始信号的信息才能准确重建原始信号。这就要求设计的测量矩阵Φ和稀疏矩阵Ψ不相干。文献［9］中证明了当测量矩阵是高斯随机矩阵时，能够满足与大多数稀疏矩阵不相关，因而随机测量矩阵常被用在压缩感知中。近年来很多文献［10-13］指出，对随机测量矩阵进行优化可使其与稀疏矩阵之间的相关性进一步减小，从而提高信号的重建性能。它们的基本思想是优化测量矩阵使得感知矩阵的不同列（也称为原子）间的相关性变得更小，即减小感知矩阵的Gram矩阵的非对角元素。这些测量矩阵优化方法主要是在稀疏矩阵Ψ确定的情况下来优化设计测量矩阵Φ，并未结合重构算法的特点来设计测量矩阵。

在压缩感知重构算法中，贪婪类算法由于计算复杂度低而受到广泛关注，其主要思想是通过迭代寻找稀疏信号非零分量相对应的原子，然后根据这些原子重构出原始信号。OMP是经典的贪婪算法，其重构性能与感知矩阵的相关系数有关，感知矩阵的相关性越低，越能准确识别正确的原子［8］。因此，文献［14］提出一种改进的OMP算法，本文称之为双字典正交匹配追踪算法（Two Dictionaries OMP， TDOMP），该算法通过引入一个新矩阵D（称为匹配矩阵）来识别原子，并且匹配矩阵和感知矩阵之间具有更低的相关性，从而提高原子识别的准确性。本文主要针对TDOMP算法的特点，提出了一种适用于TDOMP算法的测量矩阵优化方法，其主要思想是通过交替投影来优化测量矩阵，使得构造的匹配矩阵与感知矩阵具有更小的相关性，从而进一步提高重构性能。1维稀疏信号和2维图像重构实验验证了所提方法的性能，仿真结果显示使用优化测量矩阵的TDOMP算法的性能将明显提高。

2 用于TDOMP的测量矩阵优化算法

2.1TDOMP算法

TDOMP算法［14］是一种改进的OMP算法，它从降低感知矩阵Θ的相关性的思想出发，通过构造与感知矩阵互相关性低的匹配矩阵D来辨识正确的感知矩阵的原子。该算法用到两个字典Θ和D，因此称为双字典正交匹配追踪算法。TDOMP算法和OMP算法的区别在于感知原子阶段，OMP算法使用感知矩阵Θ对原子进行识别，而TDOMP算法使用匹配矩阵D对原子进行辨识。令感知矩阵Θ的每

给出了TDOMP算法的流程［15］。

表 1 TDOMP算法Tab. 1 TDOMP algorithm

在TDOMP算法中，为了构造与感知矩阵Θ相关性低的匹配矩阵D，其基本思想是使伪Gram矩阵G=DTΘ在Frobenius范数意义下与理想的Gram矩阵充分接近，即文献［14］采用交替投影的方法来解决上述问题，从而得到与Θ相关性低的匹配矩阵D，其具体方法如表2所示。

根据上述方法，给定感知矩阵Θ就可以得到和Θ相关性低的矩阵D。已有研究表明，OMP算法识别原子的能力依赖于感知矩阵自身的相关系数，而TDOMP感知原子的能力依赖于感知矩阵和匹配矩阵两者的相关系数。当D和Θ的相关系数低于Θ自身的相关系数时，TDOMP算法的重构性能将好于OMP算法［15］。

2.2基于交替投影的测量矩阵优化算法

本节主要研究测量矩阵的优化来进一步提高TDOMP算法的性能，其基本思想是设计测量矩阵使得伪Gram矩阵G=DTΘ=DTΦΨ在Frobenius范数意义下与理想的Gram矩阵充分接近。与式（1）不同的是，感知矩阵Θ在优化过程中可以变化，从而可以优化设计测量矩阵。仍采用交替投影的方法来求得优化的测量矩阵Φ以及与Θ相关性低的匹配矩阵D，所提算法具体如表3所示。

因此，当测量矩阵可以设计时，首先基于表3的交替投影法构造出测量矩阵Φopt和匹配矩阵D，此时观测方程为yopt=ΦoptΨs，然后由Θ=ΦoptΨ和D，利用TDOMP算法重构稀疏信号。

表 2 构造低相关性的匹配矩阵Tab. 2 Construction of matching matrix with low cross-coherence

表 3 基于交替投影的测量矩阵优化算法Tab. 3 Measurement matrix optimization method based on alternative projection

3 仿真实验

本节对所提的针对TDOMP重构算法的测量矩阵优化方法进行仿真，分析测量矩阵优化前后对重构性能的影响。

3.11维稀疏信号仿真实验

假设稀疏信号x=Ψs，稀疏矩阵Ψ为高斯随机矩阵或者离散余弦变换（Discrete Cosine Transform，DCT）矩阵；稀疏系数s为高斯稀疏信号或者0-1稀疏信号。对信号x采用不同的测量矩阵进行观测，然后采用OMP算法和TDOMP算法来重构稀疏系数。下面主要从准确重构概率和重构误差来比较测量矩阵优化前后的重构性能。若重构的稀疏系数满则认为准确重构，准确重构概率为准确重构次数与总重构次数的比值。重■构误差采用均方根误差，其定义为

仿真中主要比较4种情况：采用Gaussian随机阵的OMP算法（用--*表示）、采用Gaussian随机阵的TDOMP算法（用--o表示）、采用优化测量矩阵的OMP算法（其中优化算法为Duarte［10］所提，用--表示）、采用所提优化测量矩阵的TDOMP算法（称为Optimized TDOMP，用--☆表示），如表4所示。

表 4 仿真说明Tab. 4 Simulation description

仿真实验1：稀疏信号长度n=128，稀疏基Ψ为128×128，测量矩阵Φ为64×128。给定测量数m=64的情况下，观察不同测量矩阵下的准确重构概率和重构误差随信号稀疏度k变化的情况。每个稀疏度下，独立重复500次仿真实验。

稀疏基为高斯随机矩阵，稀疏系数为高斯稀疏信号和0-1稀疏信号的结果如图1和图2所示。可以看出，在测量数m固定不变的情况下，随着稀疏度k的增加，信号的准确重构概率降低，重构误差增大。采用所提优化的测量矩阵的TDOMP算法的重构效果最好，但优化测量矩阵对TDOMP算法重构性能的提高程度不如优化测量矩阵对OMP算法重构性能的提高程度。

图 1 高斯稀疏基下OMP和TDOMP算法重构高斯稀疏系数的性能比较Fig. 1 The performance comparison of recovering Gaussian sparse coefficients by using OMP and TDOMP with Gaussian sparse basis

图 2 高斯稀疏基下OMP和TDOMP算法重构0-1稀疏系数的性能比较Fig. 2 The performance comparison of recovering 0-1 sparse coefficients by using OMP and TDOMP with Gaussian sparse basis

图 3 DCT稀疏基下OMP和TDOMP算法重构高斯稀疏系数的性能比较Fig. 3 The performance comparison of recovering Gaussian sparse coefficients by using OMP and TDOMP with DCT sparse basis

图 4 DCT稀疏基下OMP和TDOMP算法重构0-1稀疏系数的性能比较Fig. 4 The performance comparison of recovering 0-1 sparse coefficients by using OMP and TDOMP with DCT sparse basis

稀疏基采用DCT矩阵，稀疏系数为高斯稀疏信号和0-1稀疏信号的结果如图3和图4所示。可以看出，采用优化测量矩阵的TDOMP算法的重构效果最好。与稀疏系数为0-1稀疏信号的情况相比，优化后的测量矩阵对高斯稀疏系数的重构效果提高得更为显著。

仿真实验2：稀疏信号长度n=128，稀疏基Ψ为128×128，采用高斯随机矩阵和DCT矩阵，稀疏系数为高斯稀疏信号和0-1稀疏信号。给定稀疏度k，观察不同测量矩阵下的准确重构概率和重构误差随信号测量数m变化的情况。测量数m从64到96以步长4变化，每个测量数下，独立重复500次仿真实验。固定稀疏度k，当稀疏系数是高斯时，k=30；当稀疏系数为0-1信号时，k=19。

稀疏矩阵采用高斯随机矩阵，稀疏系数为高斯稀疏信号和0-1稀疏信号的结果如图5和图6所示。稀疏矩阵采用DCT矩阵，稀疏系数为高斯稀疏信号和0-1稀疏信号的结果如图7和图8所示。可以看出，在稀疏度k固定不变时，随着测量数m的增加，信号的准确重构概率增加，重构误差下降。实验结果表明，采用优化的测量矩阵的TDOMP算法的重构效果最好。

3.22维图像信号仿真实验

为了进一步验证测量矩阵优化算法的性能，本节将对2维图像信号进行重构实验。源图像采用256×256的Lena图像，如图9所示。稀疏基采用DCT基。重构效果采用PSNR （Power Signal-to-Noise Ration）值来进行评价，其计算公式为：当测量值为140（即压缩比m/n=0.55）时，给出4种情况下的仿真结果，如图10所示。

图 5 高斯稀疏基下OMP和TDOMP算法重构高斯稀疏系数的性能比较Fig. 5 The performance comparison of recovering Gaussian sparse coefficients by using OMP and TDOMP with Gaussian sparse basis

图 6 高斯稀疏基下OMP和TDOMP算法重构0-1稀疏系数的性能比较Fig. 6 The performance comparison of recovering 0-1 sparse coefficients by using OMP and TDOMP with Gaussian sparse basis

图 7 DCT稀疏基下OMP和TDOMP算法重构高斯稀疏系数的性能比较Fig. 7 The performance comparison of recovering Gaussian sparse coefficients by using OMP and TDOMP with DCT sparse basis

图 8 DCT稀疏基下OMP和TDOMP算法重构0-1稀疏系数的性能比较Fig. 8 The performance comparison of recovering 0-1 sparse coefficients by using OMP and TDOMP with DCT sparse basis

图 9 原始图像Fig. 9 Original image

图 10 在不同测量矩阵下OMP和TDOMP算法的重建图像Fig. 10 Reconstructed images by using OMP and TDOMP with different measurement matrix

图10中，图10（a）为采用高斯随机测量矩阵下OMP的仿真结果，图10（b）为采用高斯随机测量矩阵下TDOMP的仿真结果，图10（c）为采用Duarte［10］所提优化测量矩阵下OMP的仿真结果，图10（d）为采用本文所提优化测量矩阵下TDOMP的仿真结果，测量矩阵优化情况下的TDOMP称为Optimized TDOMP。从图10可以看出，TDOMP算法对图像的重构效果好于OMP算法的重构能力，而对于TDOMP算法，测量矩阵优化后对图像的重构效果好于没有优化的测量矩阵的重构效果。但优化测量矩阵对TDOMP算法重构性能的提高程度不如优化测量矩阵对OMP算法重构性能的提高程度。

4 结束语

本文研究了针对特定重构算法TDOMP的测量矩阵优化方法。TDOMP算法通过构造与感知矩阵相关性低的匹配矩阵来提高原子识别的准确性。所提测量矩阵优化方法首先利用交替投影法构造相关性低的感知矩阵和匹配矩阵，然后基于其中的新感知矩阵利用最小二乘实现测量矩阵的优化。最后，通过对1维稀疏信号和2维图像的仿真实验，验证了该优化测量矩阵显著提高了TDOMP算法的重构性能。

［1］Donoho D L. Compressed sensing［J］. IEEE Transactions on Information Theory， 2006， 52（4）： 1289-1306.

［2］Candes E J， Romberg J， and Tao T. Robust uncertainty principles： exact signal reconstruction from highly incomplete frequency information［J］. IEEE Transactions on Information Theory， 2006， 52（2）： 489-509.

［3］Tsaig Y and Donoho D L. Extensions of compressed sensing［J］.Signal Processing， 2006， 86（3）： 549-571.

［4］Ender J H G. On compressive sensing applied to radar［J］. Signal Processing， 2010， 90（5）： 1402-1414.

［5］Sharma S K， Patwary M and Abdel-Maguid M. Spectral efficient compressive transmission framework for wireless communication systems［J］. IET Signal Processing， 2013，7（7）： 558-564.

［6］Majumdar A and Ward R K. On the choice of compressed sensing priors and sparsifying transforms for MR image reconstruction： an experimental study［J］. Signal Processing：Image Communication， 2012， 27（9）： 1035-1048.

［7］Kim S， Koh K， Lustig M， et al.. An interior-point method for large scale l1regularized least squares［J］. IEEE Journal of Selected Topics in Signal Processing， 2007， 1（4）： 606-617.

［8］Tropp J A. Greed is good： algorithmic results for sparse approximation［J］. IEEE Transactions on Information Theory， 2004， 50（10）： 2231-2242.

［9］Donoho D L， Elad M， and Temlyakov V N. Stable recovery of sparse overcomplete representations in the presence of noise［J］. IEEE Transactions on Information Theory， 2006，52（1）： 6-18.

［10］Duarte J M and Sapiro G. Learning to sense sparse signals：simultaneous sensing matrix and sparsifying dictionary optimization［J］. IEEE Transactions on Image Processing，2009， 18（7）： 1395-1408.

［11］Abolghasemi V， Ferdowsi S， and Sanei S. A gradient-based alternating minimization approach for optimization of the measurement matrix in compressive sensing［J］. Signal Processing， 2012， 92（4）： 999-1009.

［12］Elad M. Optimized projections for compressed sensing［J］. IEEE Transactions on Signal Processing， 2007， 55（12）：5695-5702.

［13］Xu J， Pi Y， and Cao Z. Optimized projection matrix for compressive sensing［J］. EURASIP Journal on Advances in Signal Processing， 2010： 560349.

［14］Schnass K and Vandergheynst P. Dictionary preconditioning for greedy algorithms［J］. IEEE Transactions on Signal Processing， 2008， 56（5）： 1994-2002.

［15］Zhao Juan， Bai Xia， Bi Shi-he， et al.. Coherence-based analysis of modified orthogonal matching pursuit using sensing dictionary［J］. IET Signal Processing， 2015， 9（3）：218-225.

Measurement Matrix Optimization Method for TDOMP Algorithm

Zhao Juan Bai Xia
（School of Information and Electronics， Beijing Institute of Technology， Beijing 100081， China）

Optimizing the measurement matrix can improve reconstruction performance in compressed sensing. In this study， we study the measurement matrix optimization method regarding its application to the Two Dictionaries Orthogonal Matching Pursuit （TDOMP） algorithm. The TDOMP is a modified OMP， which uses a matching matrix with low cross-coherence to identify the correct atoms of the sensing matrix. The proposed optimization method is based on alternative projection technique to construct the measurement and matching matrices with low cross-coherence to improve the performance of the TDOMP. Experimental results verify the effectiveness of the proposed method.

Compressed Sensing （CS）； Measurement matrix； Gram matrix； Mutual coherence

s： The National Natural Science Foundation of China （61421001， 61331021）， Beijing Higher Education Young Elite Teacher Project （YETP1159）

TN911.7

A

2095-283X（2016）01-0008-08

10.12000/JR15131

赵 娟（1975-），女，四川人，北京理工大学信息与电子学院副教授，博士，主要研究领域为压缩感知理论及应用。

E-mail： juanzhao@bit.edu.cn

白 霞（1978-），女，辽宁人，北京理工大学信息与电子学院讲师，博士，主要研究领域为SAR信号处理。

E-mail： bai@bit.edu.cn

2015-12-26；改回日期：2016-01-24；网络出版：2016-02-17

赵娟 juanzhao@bit.edu.cn

国家自然科学基金（61421001， 61331021），北京市高等教育青年英才资助课题（YETP1159）