1. 引言
Donho、Candes和Tao等人 [1] 在研究高度欠定的核磁共振成像问题时,正式提出了压缩感知的概念。压缩感知,也被称为压缩传感,它的基本思想是利用特定的矩阵,将K-稀疏的高维信号空间变换为低维信号空间,利用稀疏性信号的先验条件,通过某个线性或者非线性重建模型重建原始信号。压缩感知理论广泛应用于雷达探测、图像处理、无线传感网络等很多领域。压缩感知问题的求解备受关注。
压缩感知问题的模型如下:
(1)
其中,A代表
(
)的观测矩阵,x表示原始信号,且
,y代表观测值,且
。
表示向量x的零范数(即非零元的个数)。求解问题(1),需要列出x中所有非零位置的线性组合,有
种。问题(1)的数值计算很不稳定,并且是一种NP (Nondeterministic Polynomially)难的非凸优化问题。具有代表性的求解方法有匹配追踪(MP) [2],正交匹配追踪(OMP) [3],稀疏自适应匹配追踪(SAMP) [4] 等。Donohoh、Candes和Tao等人在文献 [5] 中将其转化成与之等价的
范数进行求解,证明了若观测矩阵A满足RIP (Restricted Isometry Property),那么问题(1)与
范数问题等价,并且建立了问题(1)的等价形式如下 [6]:
(2)
本文用罚函数法,将问题(2)转化为与其同解的无约束问题:
,
其中,
。
KL不等式作为收敛性分析中的一个重要研究工具,并且应用广泛。像半代数函数、tame函数、向量范数等等都是KL函数。早在1963年S. Łojasiewicz [7] 在实分析函数中,研究一般的最速下降曲线问题解的轨迹是否为有限长度时,提出Łojasiewicz不等式:
,
,
其中,
的实解析函数,
为临界点且
,
。并由此推导出最速下降曲线
的解的轨迹是有限长度,有界轨迹收敛到临界点。随后,Kurdyka [8] 将这一结果扩展到可在o-minimal结构中定义的可微函数中,相应的广义不等式称之为KL不等式。本文主要建立与其同解的无约束优化问题模型的KL性质,从而设计基于BB (Barzilai-Borwein)步长线搜索算法。
2. 预备知识
对于给定的广义实值函数
,若
,
则称
是正常的。对给定的
与
,记
。
对于给定的
和
,
表示以
为中心,
为半径的闭球。x到S的距离定义为
。
定义1 [9] (Kurdyka-Łojasiewicz性质)设
是正常的下半连续的函数。考虑任意
。若存在常数
,满足如下条件的连续凹函数
:
1)
且
在开区间
上连续可微;
2) 对所有的
,
,以及点
的邻域U使得对所有
,都有下述不等式成立
,
则称函数f在点
处具有KL性质。若f在集合
中的每点都具有KL性质,则称f是KL函数。
定义2 [10] (Lipschitz连续)设F为从集合
到
上的单值映射。设
。F在X上是Lipschitz连续的,若存在
,满足
。
其中
称为F在X上的Lipschitz常数。
定义3 [10] (次微分)函数
在x处的所有次梯度的集合称为
在x处的次微分,即
。
。
定义4 [11] 设存在
,S是一非空子集,满足
,
,令
是一正的常数。称
阶增长条件在S上成立,若存在常数
,存在S的邻域V,满足对所有的
,下述不等式成立:
。
尤其,若
,称一阶增长条件成立,若
,称第二阶(或二阶)增长条件成立。
定义5 [11] (凸函数)设C是一凸集合,
是一增广实值函数。对任意
,
,有
,
。
则函数f是C上的凸函数。
引理1 对任意给定的
,
。
注记1 根据文献 [12] 中的引理2.1,一个正常函数在所有非稳定点处具有KL性质。因此为了证明它是KL函数,只需证明函数在任意稳定点处是否具有KL性质。
注记2 若
,则称
是函数f的稳定点,记
为f的稳定点集。
3. 主要结果及其应用
考虑如下问题模型
, (3)
其中,
(
),
,
,
为参数,
,
。
记
,
,则
。
引理2 [13] 对于任意的
,给定
,则p范数,即
,具有KL性质。
由引理2知,
具有KL性质。
引理3 [14] 假设
在
上具有
的Lipschitz连续梯度,即
。
且
是下有界的。则
。
定理1 假设
在
上局部Lipschitz连续,对
,若
在
点处满足二阶增长条件,即
,
则
为KL函数。
证明:由
,
,可知
和
。因此
是凸的,且在
点满足二阶增长条件。由次微分定义,有下式成立
。
即
。
因此有
。 (4)
由于
在
点处二阶增长条件,可得
。 (5)
将(4)和(5)结合,可得
。
即
。 (6)
考虑
,
,其中
,有
,
,
则
在
上是凹函数。所以对于
,
,有
。
将(4)式与上式结合,可得到下式
。(7)
由距离函数的定义,有
。 (8)
再将(7)式与(8)式结合,得
。(9)
将(6)式带入(9)式,就可以得到
。
故
在
点处满足KL性质。由
的任意性,则
在集合
中的每点都具有KL性质,即
是KL函数。
由于函数
在
处具有连续性,因此对
,
有下式成立
。
由
是KL函数。 结合定义1,对
有下式成立:
。 (10)
令
和
。对
,有
。 (11)
由
是闭集,则
,满足
。由于
在
处具有局部Lipschitz连续性,结合引理3,有
。结合引理1中的
的表达式以及式(11),有
。 (12)
通过式(11)和式(12),有下式:
。 (13)
将
与
结合,可以得到
。由式(10)和(13),有
。
上述不等式说明了
在
处具有KL性质。由于
在
中的任意性,故
是KL函数。
4. 非单调线搜索收敛算法
本节将采用非单调线搜索算法求步长,采用BB [15] 步长作为每次迭代的初始步长,经过有限步的线搜索,就可以找到符合收敛条件的步长,该算法充分说明了该问题模型满足KL性质,基于KL性质可以分析算法的收敛性。
令
,Hessian矩阵
,其中
,则牛顿迭代为
。 (14)
用BB法可以得到Hessian矩阵
,其中
,I为
单位矩阵。将(14)式中的
替换为
,得到
。 (15)
设
,
,则
。
即
。
将上式中的
替换为
,得到
,所以
,即
。令
,迭代格式(15)也可以写为
。 (16)
BB法选取的步长,满足下式:
,
。
即步长为
,
, (17)
则
为第k次迭代的初始步长。设L是
的特征值中最大的一个数,初始步长
,为了保证全局收敛性,非单调步长准则,如下式
。 (18)
其中
满足
,
,
,
,
。
算法的具体步骤如下:
输入:
;
输出:
步骤1:初始化
,
;
步骤2:当
时,向下进行;否则停止计算;
步骤3:当
时,
;否则向下进行;
步骤4:迭代
;
步骤5:通过(17)式获取步长
,且满足
,再计算
,
;令
,返回步骤2。
变量
实际上为本次搜索准则的参照函数值,即充分下降性质的起始准则;
是函数值
和
的凸组合,并不是仅仅依赖于
,而凸组合的两个系数由参数
决定。这就说明
包含之前算过的所有目标函数值。综上所述,本文提出的算法是可行有效的。
5. 实验结果分析及讨论
通过MATLAB实验来证明该算法在重构信号方面的优势,实验运行平台的配置如下:Intel(R)Core (TM)i5-10400F CPU @2.90 GHz;内存16.00 GB。在不同的MATLAB版本测试下,结果不会发生较大变化。本文实验在MATLAB R2020b中进行。
实验取
,
,
,a表示原始信号中非零元的个数。其中非零元的位置均是随机选取的,A是与高斯矩阵独立同分布的随机矩阵 [16],
,其中
,
是分布为
的高斯噪声,取
,
,
。在线搜索过程中,选取初始步长
,
,
。相对误差定义为
,
其中
表示重构信号,
表示原始信号。相对误差用来测量重构信号的质量。当相邻两点的相对误差充分小,即
,
时,则停止迭代。原始信号,观测向量及重构信号如图1所示。
比较图1中的(a)和(c)可以分析出来,所有的蓝点均被红点包围,这说明原始信号几乎被精确重构。上述实验表明,该算法效果良好,相对误差较小,为恢复大的稀疏信号提供了一种有效的方法。
本文在接下来的实验中,采用了4种不同的信号,对不同的算法进行比较分析。取上述实验中的初始参数,对NBBL1n和NBBL1这2种算法进行了对比和分析。在初始和终止条件相同的情况下,从函数值下降的角度分析,无论针对那种信号,NBBL1n算法下降总是最快的,迭代次数也最少,为进一步说明结果,表1和表2给出了详细的对比数据。由于设下随机种子,所以每次获取的信号是不变的。所以误差很小。
(a) 原始信号
(b) 观测向量
(c) NBBL1n (RelErr = 1.38%)
Figure 1. The effectiveness of the NBBL1n algorithm
图1. NBBL1n算法的有效性
![](Images/Table_Tmp.jpg)
Table 1. Comparison of the number of iterations of the time required by the algorithm for different sparsity degrees
表1. 对于不同稀疏度,算法所需要的时间的迭代次数对比
表1中详细的列出了4种不同信号的运行时间和迭代次数。从表中可以分析出,随着信号规模的不断增大,运行算法所需要的时间也明显增加,但是通过对比,新版本算法的运行总用时较少,迭代次数也比较少。
![](Images/Table_Tmp.jpg)
Table 2. When c taken 0.4, each step iterative gradient norm vs
表2. 取
时,每步迭代梯度范数与
的对比
表2取稀疏度为0.04,为了表示一般性,45次迭代做了对比分析,充分说明了新算法满足KL不等式。再对比表1,可以得到,满足KL性质的非单调线搜索算法,无论稀疏度如何,算法均可以达到最优。
6. 结束语
本文将结合非单调线搜索算法和BB步长,在满足KL性质的基础上,将算法应用于压缩感知问题模型,数值实验结果表明,当原始信号的稀疏度不同时,该方法是可行有效的。本文的方法无论是从运行时间还是迭代次数上均有不同程度的改进。但将本文的非单调线搜索应用到其他问题中是否有较好的效果,仍需要进一步研究。
基金项目
辽宁省教育厅科学研究一般项目(LJ2019005)。
NOTES
*通讯作者。