基于PRP共轭梯度的重构算法研究

刘 艳，李 雷

(南京邮电大学 非结构化数据计算理论与应用研究中心，江苏 南京 210046)

基于PRP共轭梯度的重构算法研究

刘 艳，李 雷

(南京邮电大学 非结构化数据计算理论与应用研究中心，江苏 南京 210046)

SL0算法是一种基于近似l0范数的压缩感知信号重建算法。通过寻找一个光滑函数近似l0范数，从而将l0范数最小化问题转化为光滑函数的最优化问题，采用最速下降法和梯度投影原理逐步逼近最优解。针对求解函数的最优化问题，NSL0算法提出用修正牛顿法对双曲正切函数进行求解，但此算法需求解函数的HESS矩阵，计算量较大，影响重构速度。文中提出一种重构速度更快的基于光滑l0范数和PRP共轭梯度法的重构算法—PRPSL0。用双曲正切函数近似l0范数得到一个新的最优化问题，采用PRP共轭梯度法以及梯度投影原理推导出下降方向并逐步逼近问题的最优解。实验结果表明，在相同的测试条件下，该算法在收敛速度及重建效果方面均优于其他算法。

压缩感知；重构算法；光滑函数；共轭梯度法

1 概 述

压缩感知[1-5](Compressive Sensing,CS)，又称压缩采样，是近几年出现的一种新型压缩采样方法。该理论是指对可压缩的信号通过远低于Nyquist标准的方式进行数据测量，同时仍能精确恢复出原始信号。

根据压缩感知[3-5]理论，只要信号是可压缩的或在某个变换域上是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构原信号。

在压缩感知处理过程中，主要分为三个阶段：

(1)具有稀疏表示能力的过完备字典设计；

(2)满足非相干性或等距约束性准则的测量矩阵设计；

(3)快速鲁棒的信号重构算法设计。

重构算法的设计是压缩感知理论中关键的一部分，它对于压缩后信号的精确重构以及采样过程中的准确性验证均有着重要的意义。Candès等证明了信号重构问题可以通过求解l0范数最小化问题加以解决。文中将讨论压缩感知图像重构中的l0范数最小化问题。

压缩感知理论的基本原则和目标就是从较少的相对不完整的测量值b=Ax中恢复出k稀疏(对于长度为N的向量(实际上是指一个N维离散信号)来说，它的N个元素值只有k个是非零的，其中k≪N)的信号x∈Rn。理论上，恢复信号x最简单的方法是求解模型(1)的最小化问题。

(1)

其中，‖x‖0为x中非零元素的个数；b为测量向量；A为m×n维的测量矩阵且m

文中提出一种基于l0范数和PRP共轭梯度法的重构算法，寻找一个能够近似l0范数的光滑函数，将模型(1)转化为一个最优化问题，结合PRP共轭梯度法求解函数的最优解。

2 SL0算法基础

l0范数定义为x=[x1,x2,…，xN]T中非零元素的个数，换句话说

(2)

(3)

由此可知x=[x1,x2,…，xN]T的l0范数是由不连续函数f(x)决定的，如果能够寻找一个光滑连续的函数来替代f(x)，那么l0范数的最小化问题也可以间接求出。为了保证近似的效果，将引入一个含有参数σ的连续函数来解决l0范数的最小化问题。

定理1：若函数族fσ能够近似满足KroneckerDelta公式：

(4)

或者

(5)

那么求解l0范数问题可以转化为求解该函数族fσ和的问题。

(6)

那么对于一个函数族fσ(xi)，式(6)可以进一步转化为：

(7)

则求解x的l0范数就是求解

(8)

若函数族fσ满足式(5)，那么式(2)可以转化为：

(9)

求解式(3)即是求解

(10)

得证。

能够满足该性质的函数有很多，SL0[9]算法则选取了光滑连续的高斯函数族(见式(11))来近似l0范数[10-12],将l0范数最小化问题转化为一个连续函数的极小化问题。

(11)

(12)

SL0算法使用最速下降法和梯度投影原理来求解l0范数最优解，但是最速下降的探索路径出现了“锯齿”形状，具有不能求出全局最优解的缺点，同时其搜索路径难以估计。因此，最速下降法具有慢收敛性的缺点。文献[13]提出了复合三角函数(见式(13))来近似l0范数。

(13)

由于牛顿法具有收敛速度快的优点，因此文献[13]用牛顿法寻求最优解。

相比较于最速下降法和牛顿法，共扼梯度法既克服了最速下降法的慢收敛性，又避免了Newton法计算量大和局部收敛性的缺点。因此，文中提出使用共扼梯度法来求解模型(1)的最优解。

3 基于SL0的一种改进算法

3.1 函数的选择

SL0算法的第一步是选择一个连续光滑的函数来近似l0范数，文中将选择文献[13]中提到的双曲正切函数来近似l0范数。

(14)

其中，σ为参数；xi为是X的第i个分量。

由式(9)可以推出

(15)

定义:

(16)

由l0范数的定义可知，模型(1)中‖x‖0表示x中非零元素的个数，因此，l0范数可以近似地表示为：

(17)

综上，模型(1)可以表示为：

(18)

当σ=0时，‖x‖0=Gσ(X)，所以式(13)的解就是模型(1)的解，当σ最小且Gσ(X)最小时可以求出使l0范数最小化的量，但实际应用中σ无法取到0，因此选择一个递减序列σ1,σ2…，对每一个σi对应的目标函数求最优解，直到σ足够小为止。

3.2 基于共扼梯度法的重构算法

求解式(18)的方法有很多，各种求解的方法都有其优缺点。最速下降法主要存在两个问题：探索路径存在“锯齿现象”，影响收敛速度；搜索步长难以估计。牛顿法则很好地弥补了最速下降法的缺点，在文献[13]中提到用阻尼牛顿法来确定步长，很大程度上提高了收敛速度，但是牛顿法需要在求解Hess矩阵的同时保证矩阵是正定的，因此计算的复杂度较大。

针对以上问题，文中提出的共扼梯度法既克服了最速下降法的慢收敛性，又避免了Newton法计算量大和局部收敛性的缺点[14]。共轭梯度法的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭方向基本性质，该方法具有二次终止性。共轭梯度法中可行的下降方向是d(k)=-G(xk)+βkd(k-1)。其中，βk可由Fletcher-Reeveshe[15]和Polak-Ribiere-Polyak公式得到。当算法产生一个较小误差时，PRP公式得到的下一个搜索方向会自动靠近目标函数的负梯度方向，从而保证方向的下降性，且实践证明Polak-Ribiere-Polyak算法优于FR算法，因此文中将使用Polak-Ribiere-Polyak公式得到的βk计算搜索方向。

因此PRP共轭梯度SL0算法的具体步骤如下：

迭代过程：

forj=1,2,…,J

1)σ=σj

fork=1,2,…,L

(1)可行的下降方向：

d(k)=-G(xk)+βkd(k-1)

其中，β由Polak-Ribiere-Polyak公式得到。

(2)梯度投影法求解可行方向：

d(k)=(I-AT(AAT)-1A)d(k)

(3)由精确一维搜索确定步长μ：令xk=xk-1+μd(k)

4 实验结果及分析

为了说明文中提出的算法的优越性，将使用Matlab进行测试。文献[10]将NSL0与GP、GPSR、OMP等算法进行比较，并验证NSL0比其他算法重构性能好。因此，文中将比较SL0、NSL0、CGSL0以及PRPSL0四种算法的性能。图1给出了压缩比为0.5时四种算法的重构效果图。

图1 算法重建效果对比图

表1为在压缩比M/N=0.5时，SL0,NSL0,CGSL0以及PRPSL0在均方误差、峰值信噪比和重构时间方面的对比结果。

表1 同一压缩比下各算法重建性能对比

由表1可以看出,SL0,NSL0和CGSL0的均方误差都大于PRPSL0，PRPSL0的峰值信噪比相对于其他算法没有提高太多，但重构时间比SL0少了1.5s。由此可以看出，PRPSL0的重构性能高于其他三种算法，重构效果相对较好。

表2为在压缩比为0.1～0.6时四种算法重构时间的对比结果。

表2 不同压缩比下各算法的重构时间 s

从表中可明显看出，当压缩比相同时，PRPSL0算法所需的重构时间远远少于其余三种算法。同时，随着压缩比的增大，四种算法所需的重构时间均有所减少，但相比于其他三种算法，PRPSL0算法的重构时间最少。由此可以看出PRPSL0算法在重构速度方面的优势。

图2为不同压缩比下四种算法在收敛速度、均方误差和峰值信噪比方面的性能比较。

图2 不同压缩比下各算法的性能比较

从图中可以看出，文中提出的重构算法的均方误差以及峰值信噪比在压缩比为0.3～0.8之间时，明显高于其他三种算法，在不同采样率下，PRPSL0重构时间远远少于其他三种算法。因此，在不同的采样率下，PRP共轭梯度法重构图像所需要的时间较少，收敛速度较快，重构效果好，体现了一定程度的优势。

5 结束语

在对SL0和NSL0两种算法进行研究的基础上，分析比较最速下降法和修正牛顿法[16]的优缺点。由于最速下降法收敛性较慢，并且探索路径存在“锯齿现象”，从而影响收敛速度和难以估计探索步长，而牛顿法需要求解Hess矩阵的同时保证矩阵是正定的，计算量大。针对这两种算法存在的一些不足，文中提出了基于共轭梯度法的l0范数重构算法。由于PRPSL0算法只需求解一阶导数，因此节省了很多时间，既能克服最速下降法的慢收敛性，又避免了Newton法计算量大和局部收敛性的缺点。实验结果表明，该算法在收敛速度与重构误差方面均有很大提高。今后将致力于在重构精度方面进一步优化算法，使其能够真正应用到图像及视频重构中去。

[1]CandèsE.Compressivesampling[C]//Proceedingsoftheinternationalcongressmathematicians.Madrid,Spain:[s.n.],2006:1433-1452.

[2]CandèsE,RombergJ.Quantitativerobustuncertaintyprinciplesandoptimallysparsedecompositions[J].FoundationsofComputerMath,2006,6(2):227-254.

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

[4]CandèsEJ,RombergJ,TaoT.Robustuncertaintyprinciples:exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETransactionsonInformationTheory,2006,52(2):489-509.

[5] 石光明，刘丹华，高大化，等.压缩感知理论及其研究进展[J].电子学报，2009,37(5):1070-1081.

[6]PantJK,LuWusheng,AntoniouA.Reconstructionofsparsesignalbyminimizingareweightedapproximatel0-norminthenullspaceofthemeasurementmatrix[J].IEEETransactionsonSignalProcssing,2005,53(8):3010-3022.

[7]TroppJ,GillbertA.Signalrecoveryfromrandommeasurementsviaorthogonalmatchingpursuit[J].IEEETransactionsonInformationTheory,2007,53(12):4655-4666.

[8]ChartrandR,YinW.Interativereweightednormalgorithmforcompressivesensing[C]//ProcofIEEEinternationalconferenceonacoustics.[s.l.]:IEEE,2009:3869-3873.

[9]MohimaniH,Babaie-ZadehM,JuttenC.Afastapproachforovercompletesparsedecompositionbasedonsmoothedl0norm[J].IEEETransactionsonSignalProcessing,2009,57(1):289-301.

[10] 赵瑞珍，林婉娟，李 浩，等.基于光滑l0范数和修正牛顿法的压缩感知重建算法[J].计算机辅助设计与图形学学报,2012,24(4):478-484.

[11] 林婉娟,赵瑞珍,李 浩.用于压缩感知信号重建的NSL0算法[J].新型工业化,2011,1(7):78-84.

[12] 杨良龙,赵生妹,郑宝玉,等.基于SL0压缩感知信号重建的改进算法[J].信号处理,2012,28(6):834-841.

[13] 齐焕芳,徐源浩.用于压缩感知信号重建的SL0改进算法[J].电子科技,2015,28(4):27-30.

[14] 解可新，韩 健，林友联.最优化方法[M].天津：天津大学出版社，2004.

[15] 陆 望.基于压缩感知的信号重构算法研究及应用[D].南京:南京邮电大学,2015.

[16]SunWenyu，YuanYaxiang.Optimizationtheoryandmethods[M].NewYork:Springer,2006.

Research on Reconstruction Algorithm Based on PRP Conjugate Gradient

LIU Yan，LI Lei

(Research Center of Unstructured Data Calculation Theory and Application,Nanjing University of Posts and Telecommunications,Nanjing 210046,China)

The SL0algorithmisareconstructiononeincompressivesensingbasedonapproximatel0norm.Byusingasmoothfunctiontoapproximatethel0normandturnthel0normproblemintotheoptimizationproblem,itapproachesthesolutionusingthespecificiterationprocesswiththesteepestdescentmethodandgradientprinciple.Forsolvingtheoptimizationproblem,theNSL0algorithmusestherevisedNewtonmethodtosolvethehyperbolictangentsequence,butitdemandstheHESSmatrixofthefunction，sothelargeamountofcalculationinfluencesthespeedofreconstruction.Areconstructionalgorithmisputforwardbasedonthesmoothedl0normandconjugategradientmethodcalledPRPSL0.Thehyperbolictangentsequenceisutilizedtoapproximatethel0norm,thenapplyingPRPconjugategradientmethodandgradientprincipletosolvethedropdirectionandtheoptimalsolution.Theexperimentalresultsshowthattheproposedalgorithmissuperiortootheralgorithmsbothintermsofconvergencespeedandreconstructioneffect.

compressive sensing;reconstruction algorithm;smooth function;conjugate gradient method

2015-12-02

2016-03-09

时间：2016-08-01

国家自然科学基金资助项目(61070234,61071167,61373137,61501251);南京邮电大学引进人才科研启动基金资助项目(214191);江苏省普通高校研究生科研创新计划资助项目(KYZZ15_0236)

刘 艳(1991-)，女，硕士，研究方向为非线性分析及其应用；李 雷，教授，研究方向为智能信号处理和非线性科学及其在通信中的应用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160801.0907.042.html

TP

A

1673-629X(2016)08-0055-05

10.3969/j.issn.1673-629X.2016.08.012