改进的压缩感知量测矩阵优化方法

王彩云，徐 静

（1．南京航空航天大学航天学院，江苏南京210016；2．南京航空航天大学电子信息工程学院，江苏南京210016）

改进的压缩感知量测矩阵优化方法

王彩云1，徐 静2

（1．南京航空航天大学航天学院，江苏南京210016；2．南京航空航天大学电子信息工程学院，江苏南京210016）

压缩感知理论中信号的重建要求量测矩阵与稀疏变换基之间的互相关性要尽可能小。以降低二者互相关性为目的，研究了一种改进的基于变步长梯度下降的量测矩阵优化方法。该方法利用梯度下降法更新步长，并基于模拟退火中的降温思想引入学习速率因子来进一步调节步长的变化，提高算法的收敛速度，改善算法的性能。仿真结果表明，使用变步长梯度下降法优化后的量测矩阵与稀疏变换基的互相关系数在零附近的分布更加集中，量测矩阵的优化速度快并且重构图像的峰值信噪比提高。因此，所提方法优化所得的量测矩阵无论是降低互相关性还是提高图像重建质量都具有良好的性能。

压缩感知；量测矩阵；梯度下降；变步长；优化

0 引 言

压缩感知（compressed sensing，CS）［13］是信号及图像处理领域诞生的一种崭新的数据采样理论，该理论突破了传统奈氏采样定理，在信号采样的同时实现信号压缩。由于CS理论大大降低了信息采集量、采样时间和存储空间，受到许多研究者的高度关注［46］。CS理论的核心环节是信号采样和重建，而构造合理有效的量测矩阵对于量测值获取和信号重建起着至关重要的作用。

CS理论研究表明，信号的精确恢复要求感知矩阵满足有限等距性（restricted isometry property，RIP）［7］，该性质等价于量测矩阵与稀疏基不相关［8］。近年来，针对降低量测矩阵与稀疏变换基的互相关性已开展一些研究。一类是有效投影法［9］，该方法取稀疏变换基的奇异值向量的部分列向量组成量测矩阵，从而增强稀疏变换基与量测矩阵的非相干性。一类方法是基于Gram矩阵的迭代优化方法，如：文献［10］提出基于Gram矩阵的t平均互相关性，通过阈值缩放处理减小非对角线元素；文献［11］提出基于Gram矩阵的整体互相关系数，采用特征值分解方法减小互相关系数；文献［12- 13］利用梯度下降迭代法使得Gram矩阵接近于单位阵；文献［14］采用特征值分解方法使Gram矩阵逼近于单位阵；文献［15］通过等角紧框架结构，使Gram矩阵的非对角线元素都等于矩阵的最大互相关系数。此外，文献［16］提出量测矩阵与稀疏字典联合优化，字典学习和量测矩阵优化交替进行，从而降低二者互相关性。上述文献研究表明通过减小互相关性的量测矩阵优化方法可以得到性能更优的量测矩阵，从而提高信号的重建精度，减小压缩比。

本文研究了一种改进的基于变步长梯度下降的量测矩阵优化方法。该方法在研究由量测矩阵与稀疏基构造的Gram矩阵元素的基础上，基于模拟退火中的降温思想，引入学习速率因子调节步长变化，即用变步长的梯度下降法减小二者的互相关性，用于图像重建也取得了较高的峰值信噪比（peak signal to noise ratio，PSNR）。

1 CS基本理论

设x∈Rn为长度为n的一维离散时间信号，则信号x在正交基Ψ＝｛Ψ1，Ψ2，…，Ψn｝上的线性组合表示为

原始信号通过量测矩阵Φ∈Rm×n得到量测向量

式中，D＝ΦΨ为感知矩阵。利用重建算法恢复原始信号x，即求解式（3）的1-范数优化问题。

由于m≪n，所以式（3）是一个NP-hard问题。为解决此问题，通常是寻找一组稀疏的系数矢量解。典型的求解算法有：基追踪（basis pursuit，BP）算法［17］，匹配追踪（matching pursuit，MP）和正交匹配追踪（orthogonal MP，OMP）算法［18］等。

2 改进的量测矩阵优化设计

2.1 量测矩阵优化模型设计

定义量测矩阵与稀疏基的互相关系数［8］为

由于D＝ΦΨ，因此互相关性等价为感知矩阵D各列间归一化互相关系数的最大值［19］，即

式（14）中，梯度▽βk－1J（Φk）的计算公式推导过程如下：

定义Gram矩阵G＝^DT^D，^D是D列单位化以后的矩阵，则最大互相关系数为G矩阵的非对角元素绝对值的最大值，即

由于μmax只能描述G矩阵的局部相关性，因此引入平均互相关系数来描述其整体相关性，即

式（6）中，若感知矩阵D的列向量相互正交，即μmax＝0，则G矩阵近似于单位矩阵，即

式（8）左乘Ψ和右乘ΨT得［12］

对ΨΨT进行特征值分解VUVT＝ΨΨT，代入式（9）得

令T＝VU，则量测矩阵优化模型为

由以上分析可知，满足式（11）的量测矩阵与稀疏变换基的互相关系数最小。

2.2 量测矩阵优化算法设计

本节介绍一种改进的基于变步长梯度下降的量测矩阵优化算法。首先对量测矩阵Φ进行近似QR分解以降低矩阵的线性相关性；然后利用最速梯度下降法对量测矩阵进行自适应更新，即沿目标函数最速下降的方向对其进行调整，即φij←φij－ξ∂J／∂φij，ξ＞0为步长，可得∂J／∂Φ＝4ΦT（TTΦΤΦT－U）TT，因此更新方程为

式中，k是循环迭代次数；β＝4ξ是新的步长参数。

式（12）中步长更新为

式中，参数η称为学习速率。

学习速率太小则算法的收敛性容易得到保证，但收敛速度较慢；学习速率太大则收敛速度快，但算法可能不稳定。针对以上问题，本文中引入学习速率因子γ实现学习速率η的自适应变化。

模拟退火方法中经典的降温公式为Tk＝γ×Tk－1，式中，γ为降温系数（常取稍小于1的数值），显然随着迭代次数k的增加，温度T以相同速率减小。本文中迭代初期希望步长β变动较大，需要较大的学习速率η，随着迭代的进行，越来越接近最优点，则希望β变动较小，需要较小的η，以便在最优值所在的小范围内搜索寻优。因此学习速率η的变化可以通过降温系数γ实现，本文中定义为学习速率因子，γ的引入使学习速率η在迭代过程中不断减小，从而实现步长β随着迭代由大到小的变化，此时步长β的更新公式为

首先定义矩阵的内积公式［20］为

则梯度的计算可以转化为

由式（11）得

由式（12）得假设Lk－1＝Φk－1T（TTΦTk－1Φk－1T－U）TT，那么梯度的最终计算公式为

通过式（14）～式（20）可实现步长更新。

本算法中除了使用自适应学习速率以外，还明确设置了迭代终止条件，即当目标函数值在相邻迭代过程中的相对误差E满足式（21），则迭代终止，得到优化的量测矩阵。

式中，ε为门限参数，一般取10－3或更小的常数。终止条件的设置弥补了固定循环次数的不足，节省了计算时间，提高了算法性能。本文核心算法步骤如下：

步骤1 产生随机量测矩阵Φ∈Rm×n，稀疏基Ψ∈Rn×n，初始步长β0，初始学习速率η0，学习速率因子γ，迭代终止门限ε；

步骤2 对ΨΨT进行特征值分解得到ΨΨT＝VUVT，对量测矩阵Φ进行QR分解，令T＝VU，k＝1；

步骤3 利用式（12）计算新的量测矩阵Φk；

步骤4 利用式（14）和式（15）计算新步长βk；

步骤5 计算相邻迭代过程中目标函数的相对误差E，若E＜ε满足，迭代终止，执行步骤6；否则，令k＝k＋1，执行步骤2～步骤4，继续迭代；

步骤6 输出优化后的量测矩阵^Φ。

3 实验结果与分析

针对上述的算法，本节通过仿真实验验证算法的正确性和有效性。仿真条件设置如下：

实验1 量测矩阵为60×64的高斯随机矩阵，稀疏基为64×64的离散余弦变换矩阵；

实验2 选取256×256的Lena图像为实验对象，量测矩阵为m×256的高斯随机矩阵和循环矩阵，量测数目m在20～200范围内变动，稀疏基为256×256离散小波变换矩阵。

3.1 量测矩阵优化仿真

实验1 参数设置：β0＝0.01，η0＝10－2，ε＝0.001，γ＝0.5～0.9。图1为在学习速率因子γ取不同值时，最大互相关系数μmax的变化曲线。

图1 最大互相关系数μmax随γ取值的变化

图1 表明，随着迭代次数的增加，μmax的值不断减小，且学习速率因子γ的取值越大，在μmax最终收敛取值相当时，γ＝0.9时的收敛速度最快。表1所示γ＝0.9时，本文方法与前人方法的μmax，μav的比较。图2给出运算时间t随量测数目m的变化曲线。

表1 不同方法所得的μmax，μav比较

图2 运算时间t随量测数目m的变化曲线

将不同方法优化后的量测矩阵与稀疏变换基的互相关系数的绝对值以0．025为间隔进行统计，给出统计直方图如图3所示。

图3 量测矩阵与稀疏基之间的互相关系数统计分布

由表1可见，本文算法得到的量测矩阵与稀疏基的最大互相关系数、互相关系数的平均值均最小，说明本文算法在降低最大互相关系数的同时使得互相关系数的平均值也明显降低，意味着信号恢复时所需量测数目更少。由图2可见，量测值在20～60间变动时，不同方法的运算时间的变化情况，可以看出，本文算法的运算时间低于其他3种方法，运算时间降低，表明算法性能得到提高。

图3表明，经过本文优化后的相关系数的分布范围缩小且在零值附近的分布更加集中，达到降低互相关系数的目的。以上分析说明经过本文方法处理后整体性能得到提升。

3.2 图像重构仿真

实验2 参数设置：β0＝0.002，η0＝10－3，ε＝0.000 1，γ＝0.9，重构算法选取OMP算法。

（1）量测数目m对重构效果的影响分析：实验中量测值m从20到200变化，重构图像PSNR随m的变化曲线如图4所示。

图4 重构图像的PSNR随量测数目m的变化

由图4可知，经过本文方法优化后的量测矩阵用于重建图像的PSNR显然高于其他两种方法，更高于未经优化的量测矩阵图像重建效果。

（2）Lena图像的重构效果比较：选取量测值为m＝200，PSNR为图像重构效果好坏的衡量标准，PSNR值越高重构效果越好。

图5给出了量测值m为200时Lena图像重建效果。由PSNR值对比可知，本文方法重建图像的质量优于Abolghasemi和王红梅方法重建图像的质量。此外，量测数一定时本文方法迭代次数平均为25次，比其他两种方法的迭代次数至少减少50%，优化效率提高。

图5 量测矩阵为200×256的高斯矩阵重建图像

4 结 论

本文给出了一种改进的基于变步长梯度下降的量测矩阵优化方法。以降低量测矩阵与稀疏变换基之间的互相关性、提高信号重建精度为目的，借鉴模拟退火的降温思想，引入学习速率因子调节步长的变动，改进了基于梯度下降的量测矩阵优化方法。实验结果表明，本文方法优化后的量测矩阵与稀疏变换基的互相关系数以及互相关系数的均值都最小，算法的收敛速度加快，图像重构后的PSNR提高，证明本文提出的量测矩阵优化方法是可行且有效的。

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

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

［3］Elad M，Michal A．Image denoising via sparse and redundant representations over learned dictionaries［J］.IEEE Trans.on Image Processing，2006，15（12）：3736- 3745.

［4］Chang H，Lu G Y，Feng J Y．Unambiguous wideband DOA estimation based on compressed sensing［J］.Systems Engineering and Electronics，2013，35（5）：920- 923．（常虹，卢光跃，冯景瑜．基于压缩感知的无模糊宽带测向技术［J］．系统工程与电子技术，2013，35（5）：920- 923．）

［5］Zhou T Y，Tao D C．1-bit hamming compressed sensing［C］∥Proc.of the IEEE International Symposium Information Theory，2012：1862- 1866.

［6］Ling X X，Wei Z H，Xiao L，et al．Compressive sensing image reconctruction algorithm based on non-local regularization［J］. Systems Engineering and Electronics，2013，35（1）：196- 202．（李兴秀，韦志辉，肖亮，等．非局部正则化的压缩感知图像重建算法［J］．系统工程与电子技术，2013，35（1）：196- 202．）

［7］Candes E．The restricted isometry property and its implications for compressed sensing［J］.Comptes Rendus Mathematique，2008，346（9／10）：589- 592.

［8］Baraniuk R．A lecture on compressive sensing［J］.IEEE Signal Processing Magazine，2007，24（4）：118- 121.

［9］Nhat V D M，Vo D，Challa S，et al．Efficient projection for compressed sensing［C］∥Proc.of the Computer and Information Science，2008：322- 327.

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

［11］Zhao R Z，Qin Z．An optimization method for measurement matrix based on eigenvalue decomposition［J］.Signal Processing，2012，28（5）：654- 656．（赵瑞珍，秦周．一种特征值分解的量测矩阵优化方法［J］．信号处理，2012，28（5）：654- 656．）

［12］Abolghasemi V，Ferdowsi S，Makkiabadi B，et al．A robust approach for optimization of the measurement matrix in compressed sensing［C］∥Proc.of the International Workshop on Cognitive Information Processing，2010：388- 392.

［13］Wang H M，Yan J．Optimization method of measurement matrix used of mutual coherence matrix in the compressed sensing［J］. Electronic Measurement Technology，2012，35（11）：117- 118．（王红梅，严军．一种利用自相关优化压缩感知量测矩阵的方法［J］．电子测量技术，2012，35（11）：117- 118．）

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

［15］Xu J P，Pi Y M，Cao Z J．Optimized projection matrix for compressive sensing［J］.Eurasip Journal on Advances in Signal Processing，2010：1- 9.

［16］Endra M．Joint optimization of measurement matrix and sparse dictionary in compressive sensing［C］∥Proc.of the International Conference on Chemistry and Chemical Engineering，2012：3- 5.

［17］Chen S S，Donoho D L，Saunders M A．Atomic decomposition by basis pursuit［J］．Society for Industrial and Applied Mathematics Journal on Scientific Computing，1998，20（1）：33- 61.

［18］Huang S S，Zhu J B．Recovery of sparse signals using OMP and its variants：convergence analysis based on RIP［J］.Inverse Problems，2011，27（3）：2- 10.

［19］Zhang J D，Zhang G，Pan H，et al．Optimized sensing matrix design of filter structure based compressed sensing radar［J］. Acta Aeronautica et Astronautica Sinica，2013，34（4）：866-868．（张劲东，张弓，潘汇，等．基于滤波器结构的压缩感知雷达感知矩阵优化［J］．航空学报，2013，34（4）：866- 868．）

［20］Yuan L X，Wang W W，Chambers J A．Variable step-size sign natural gradient algorithm for sequential blind source separation［J］.IEEE Signal Processing Letters，2005，12（8）：589- 592.

Improved optimization algorithm for measurement matrix in compressed sensing

WANG Cai-yun1，XU Jing2
（1.College of Astronautics，Nanjing University of Aeronautics&Astronautics，Nanjing 210016，China；2.College of Electronic and Information Engineering，Nanjing 210016，China）

The signal recovery performance of compressed sensing（CS）requires that the cross correlations between the measurement matrix and sparse transformed matrix should be as small as possible．In order to reduce the cross correlations，an varied step gradient descent algorithm is studied and si-mulated annealing（SA）learning rate factor is introduced to adjust the step function．The simulation results demonstrate that due to the adaptive adjustment of step length in the iteration process，the speed of optimizing matrix is fast，more mutual coherence coefficients are distributed around zero，and the peak signal to noise ratio of reconstructed image is improved with the optimized measurement matrix．The improved algorithm has good performance in achieving lower mutual coherence and improving reconstruction performance．

compressed sensing（CS）；measurement matrix；gradient descent；varied step；optimization

TP751

A

10．3969／j．issn．1001-506X．2015．04．05

王彩云（1975 ），女，副教授，博士，主要研究方向为雷达信号处理、压缩感知。E-mail：wangcaiyun＠nuaa．edu．com

1001-506X（2015）04-0752-05

2014- 02- 25；

2014- 09- 18；网络优先出版日期：2014- 11- 21。

网络优先出版地址：http：／／w ww．cnki．net／kcms／detail／11．2422．TN．20141121．0937．009．html

国家自然科学基金（61301211）资助课题

徐 静（1989-），女，硕士研究生，主要研究方向为压缩感知、目标识别。E-mail：xujing_ll99＠163．com