王 文，李 永

(西安电子科技大学数学与统计学院，西安陕西 710126)

1 压缩感知基础知识

随着现代科学技术的发展，人们对信息的需求给信号采样、传输和存储造成了较大压力［1］。传统的采样理论基本思想是先采样再进行压缩，但其存在诸多缺点。针对这些问题Donoho，Candes及Tao等人提出了压缩感知理论［2－4］，其基本思想是在信号采样的同时就进行压缩，然后从观测向量b中重构出原始信号A x=b，其中b是长度为m的观测向量，Am×n(m≪n)是观测矩阵，求解上述问题就需要列出x中所有非零位置的Ckn种线性组合，而上述问题的数值计算很不稳定且是一个NP难的非凸优化问题。为求解上述问题，Candes，Tao和 Donoho等人证明，当观测矩阵A满足约束等距性质(RIP)时，上述问题可转化为1－范数问题

为更容易地求解式(1)，可通过选取适当的参数μ，将之转化为与其同解的无约束问题

可看出，式(1)和式(2)是线性规划问题。但在实际问题中，需重构的信号规模较大，且通常均是病态的。所以，求解线性规划问题的一般方法不能较好地求解，故寻求其的解决方案是压缩感知理论的核心内容。

近年来已提出了多种求解上述问题的算法，大致可分为两类:其一是不改变目标函数，即求解0－范数问题，例如匹配追踪(MP)［5］、正交匹配追踪(OMP)［6］、稀疏自适应匹配追踪(SAMP)［7］、正则化正交匹配追踪(ROMP)［8］等;其二是将目标函数进行转化，即将0－范数问题转化为其他范数问题，如基追踪法(BP)［9］、投影梯度法 (GPSR)［10］、软阈值算法(FPC)［11］、坐标下降法(CGD)［12］、交替方向法(YALL1)［13］、可分离稀疏重构法(SpaRSA)［14］、内点法(l1 －ls)［15］和非单调 Barzilai－Borwein(BB)梯度法(NBBL1)［16］等。其中，NBBL1算法将 BB梯度法与非单调线搜索方法相结合应用到压缩感知问题中，获得了较好地实验效果。基于上述思想的启发，本文通过将BB梯度法与另一种非单调线搜索法相结合而提出了一种新算法来求解式(2)，该算法在未增加复杂度的同时得到了更好的理论和实验效果。

2 非单调线搜索BB梯度法

选取NBBL1算法的方向作为新算法方向，采用一种新改进的非单调线搜索法求步长，并给出了新算法的具体步骤。

2.1 NBBL1算法方向的选取

引理1［16］若dk是定义的方向，对于 λk＞0，则有以下两式成立

文献［16］中已证，其说明当dk≠0时，式(3)是下降方向，∀θ∈(0，h］，xk+ θdk是下降点。

2.2 NNBBL1算法步长的选取

NBBL1算法中采用文献［18］中的非单调线搜索法，在求最大值函数的过程中，会舍去一些目标函数值，而这些值可能对最优步长的选取有帮助，且M值的选取也会影响算法的效果［19］。

基于这样的考虑，本文采用一种新的改进的非单调线搜索法求步长［17］，并结合NBBL1算法中的方向提出一种新的非单调线搜索法BB梯度法(NNBBL1)。首先介绍新的改进的非单调线搜索法，对于光滑函数φ(x)，选取C0=φ(x0)，Q0=1，τ＞0，0≤ηmin≤ηmax＜1＜ρ，η∈

其中，hk是满足式(6)最小的正整数，Qk+1=ηkQk+1，Ck+1=(ηkQkCk+φ(xk+1))/Qk+1，ηk是决定非单调程度的因子。也可将式(4)转化为

将上述非单调线搜索法应用到式(2)，取δk，ηk为常数，记为δ，η。则式(6)和 式(7)为

其中，hk是满足式(8)最小的正整数，Qk+1=ηQk+1，Ck+1=(ηQkCk+F(xk+1))/Qk+1，Δk=gTkdk+

2.3 基于新非单调线搜索法的NNBBL1算法

算法的具体步骤如下:

第1步 初始化各个参数。任选初始点x0，C0=F(x0)，Q0=1，0≤ηmin≤ηmax＜1＜ρ，η∈［ηmin，ηmax］，δmax＜1，0 ＜δmin＜(1 －ηmax)δmax，ε＞0，τ＞0＞0，δ＞0，非负整数k:=0。

第3步 新非单调线搜索获取步长。计算Qk+1和Ck+1。选取 δmin≤δ＜ δmax/Qk+1，更新步长 αk=ρhk≤τ，使得满足式(8)。

第4步 更新迭代:xk+1=xk+αkdk，得到新的点，令k:=k+1，返回第2步。

由C0=F(x0)，则 Ck是 F(x1)，…，F(xk)的凸组合，故Ck+1是Ck和F(xk+1)的凸组合，这就意味着Ck包含之前算过的所有目标函数值。类似文献［17］可证明，满足式(6)的 δ是存在的。定理1说明满足式(8)的初始步长是存在的。综上所述，本文所提出的算法是可行有效的。

3 算法的收敛性分析

为证明算法的全局收敛性，本文要求f满足以下假设。

定理2 设αk是满足式(8)的最大步长，则有

证明 对于∀k∈N，k≥0，有F(xk)≤Ck，则Ck有下界，由式(8)得C2≤C1+ δα1Δ1，…，Ck+1≤Ck+ δαkΔk，…。将上述不等式左右分别相加得

定理3 设{xk}是由NNBBL1算法产生的迭代序列，{dk}是由式(3)产生的方向序列K，则存在一个子序列，满足

在文献［16］中已证明，对于∀k∈N，k≥0，λk＞0，h∈(0，1］，则xk是问题(2)的稳定点充要条件是dk=0。而F(x)是凸函数，则局部最优解就是全局最优解。

4 实验结果分析及讨论

通过两类Matlab实验来证明该算法在重构信号方面的优势，实验运行平台的配置如下:处理器 Intel(R)Core(TM)i3 CPU M 380@2.53 GHz;内存 2.00 GB 。在不同的Matlab版本测试下，结果不会发生较大变化。本文实验在Matlab R2011b中进行。

4.1 第一类实验

实验取 n=2 048，m=512，k=64，k表示原始信号中非零元的个数。其中非零元的位置均是随机选取的，A是与高斯矩阵独立同分布的随机矩阵，b=A x0+ω，其中 ω∈Rn是高斯白噪声，且 ωN(0，σ2I)，取 μ =2－8，σ =1e－3，ε =1e－4，h=0.8，λmin=1e－30，λmax=1e+30，为使 λk＞0，取 λk=min{λmin，max{λk，λmin}}。在线搜索过程中，选取初始步长x0=0，=0.8，ρ=0.5，δ=1e－4，η=0.4。相对误差定义为其中表示重构信号表示原始信号。当相邻两点的相对误差充分小，即时，则停止迭代。原始信号，观测向量及重构信号如图1所示。

图1 NNBBL1算法的有效性

比较图1(a)和图1(c)可看出，所有的蓝点均被红点包围，这说明原始信号几乎被精确重构。上述实验表明，该算法对一维信号的重构效果良好，且相对误差较小。

4.2 第二类实验

取n=4 096，m=1 024，采用4种不同的稀疏度对各种算法进行比较。取第一类实验中的初始参数及=5，不同的是，实验中取 x0=ATb，对 NNBBL1，NBBL1和GPSR的3种算法进行了不同角度的对比和分析，如图2和表1、表2所示。

图2 针对不同压缩比、不同算法的目标函数值下降速度比较

如图2所示，在初始及终止条件相同的情况下从函数值下降角度分析，无论针对哪种信号，NNBBL1算法总是下降最快的，其次是NBBL1算法，最后是GPSR算法。从图中横轴可看出，NNBBL1算法所需迭代次数也是最少的。

为更进一步说明图2所示结果，表1给出了更详细的对比数据。由于获取的信号是随机产生的，表1和表2中采用10次实验的平均值作为记录值。而NNBBL1和NBBL1算法的相对误差几乎一样，但明显比GPSR算法小，不再罗列。

表1 针对不同稀疏度，不同算法实现相同精度所需要的时间和迭代次数对比

表1中罗列了4种信号的运行时间和迭代次数。从表中可看出，随着信号规模的增大，各种算法所需运行的时间也明显增加，但与算法NBBL1和算法GPSR相比，无论是哪种信号，NNBBL1总是用时最少，且所需迭代次数最少。

表2 不同初始点对算法的影响效果对比

表2取稀疏度k/n=0.05，研究选取不同初始点对算法效果的影响。当初始点设为ATb时，达到最优值所需的时间和迭代次数均为最少，其次是NBBL1算法，最后是GPSR算法。这说明无论取哪个初始点，新算法均为最优。

5 结束语

本文结合新非单调线搜索的Barzilai－Borwein梯度法应用于压缩感知问题，经数值试验结果证明，针对不同稀疏度的信号，该方法均是可行有效的。与NBBL1和GPSR等算法相较，新算法无论是从运行时间或是迭代次数上均有不同程度的改进。但将新非单调线搜索方法应用到其他算法是否也有较好效果，仍需进一步研究。

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

［2］Donoho D L.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52(4):1289 －1306.

［3］Candes E J，Romberg JK，Tao T.Stable signal recovery from incomplete and inaccurate measurements［J］.Communications on Pure and Applied Mathematics，2006，59(8):1207－1223.

［4］Candès E J，Romberg J，Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transactions on Information Theory，2006，52(2):489 －509.

［5］Mallat SG，Zhang Z.Matching pursuits with time－frequency dictionaries［J］.IEEE Transactions on Signal Processing，1993，41(12):3397 －3415.

［6］Tropp J A，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2007，53(12):4655 －4666.

［7］Do T T，Gan L，Nguyen N，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing［C］.2008 42nd Asilomar Conference on Signals，Systems and Computers，IEEE，2008:581 －587.

［8］Needell D，Vershynin R.Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit［J］.IEEE Journal of Selected Topics in Signal Processing，2010，4(2):310 －316.

［9］Chen SS，Donoho D L，Saunders M A.Atomic decomposition by basis pursuit［J］.SIAM Journal on Scientific Computing，1998，20(1):33 －61.

［10］Figueiredo M A T，Nowak R D，Wright SJ.Gradient projection for sparse reconstruction:application to compressed sensing and other inverse problems［J］.IEEE Journal of Selected Topics in Signal Processing，2007，1(4):586 －597.

［11］Hale E T，Yin W，Zhang Y.Fixed－point continuation forℓ1－ minimization:Methodology and convergence［J］.SIAM Journal on Optimization，2008，19(3):1107 －1130.

［12］Yun S，Toh K C.A coordinate gradient descent method forℓ1－ regularized convex minimization［J］.Computational Optimization and Applications，2011，48(2):273 －307.

［13］Yang J，Zhang Y.Alternating direction algorithms for ℓ1 －problems in compressive sensing［J］，SIAM Journal on Scientific Computing，2011，33(3):250 －278.

［14］Wright S J，Nowak R D，Figueiredo M A T.Sparse reconstruction by separable approximation［J］.IEEE Transactions on Signal Processing，2009，57(7):2479 －2493.

［15］Kim S，Koh K，Lustig M，et al.An interior－ point method for large－scale ℓ1 － regularized leastsquares［J］.IEEE Journal of Selected Topics in Signal Processing，2007(1):606 －617.

［16］Xiao Y H，Wu SY，Qi L Q.Nonmonotone Barzilai－Borwein gradient algorithm forℓ1－regularized nonsmooth minimization in compressive sensing［J］.Journal of Scientiic Computing，2014(1):6 －10.

［17］Huang S，Wan Z，Chen X.A new nonmonotone line search technique for unconstrained optimization［J］.Journal of Computational and Applied Mathematics，2008，219(1):134 －144.

［18］Grippo L，Lampariello F，Lucidi S.A nonmonotone line search technique for Newton's method［J］.SIAM Journal on Numerical Analysis，1986，23(8):707 －716.

［19］Toint P L.An assessment of nonmonotone linesearch techniques for unconstrained optimization［J］.SIAM Journal of Science Computer，1996，17(3):725 － 739.