1. 引言
低秩矩阵逼近是一种从退化的观测中恢复低秩矩阵的方法,近年来受到了计算机视觉和机器学习界的广泛关注,并已经成功应用于各个领域,如矩阵填充、背景建模和运动分割等。
众所周知,秩极小化问题很难求解。因此,秩函数通常由凸核范数代替,这类凸问题可以由许多已知的求解器 [1] [2] [3] 有效地求解。然而,核范数是秩函数的松散近似,由核范数近似秩函数得到的解通常是次优的。为了更好地逼近秩函数,本文利用矩阵奇异值上的
范数的非凸替代族来逼近秩函数,从而提出了一种新的加权非凸非光滑最小化问题,并使用迭代加权核范数(IRNN)算法对该问题进行求解。
2. 预备知识
在这一节中,我们介绍了Lipschitz连续的定义,并引入了超梯度的概念,它将在求解非凸非光滑问题中使用。我们知道,次梯度是凸函数在非光滑点的梯度的扩展,实际上超梯度则是凹函数在非光滑点的梯度的扩展。
定义1 (Lipschitz连续)称f的梯度
为Lipschitz连续,如果对于任意
,有
(1)
称
为
的Lipschitz常数。
定义2 (次梯度)若g是凸的、非光滑的,则其在x处的次梯度为u,则下列不等式成立
(2)
定义3 (超梯度)设g是凹的,向量v是g在x点的超梯度,如果对于每一个y,有下面的不等式成立
(3)
非光滑点处的超梯度可能不是唯一的,g在x处的所有超梯度称为g在x处的超微分,并表示为
。如果g在x处可微,那么
是唯一的超梯度,即
。一些常见凹函数的超梯度如表1所示。
Table 1. Popular nonconvex surrogate functions and their supergradients
表1. 常见的非凸替代函数和它们的超梯度
对于凹函数
是凸的,反之亦然。根据这一事实,g的超梯度与
的次梯度之间存在以下关系。
引理1 设
是凹的,
。对于任何
,
成立,反之亦然。
引理1给出了超梯度与次梯度的关系,从而得到了超梯度的一些性质。众所周知,对于任何
,
,凸函数h的次微分称为单调算子,即
(4)
凹函数的超微分则具有如下相反的性质。
引理2 对于任何
,
,凹函数g的超微分称为反单调算子,即
(5)
根据引理2,假设
是凹的。如果
,那么对于任意
和
都有
。
引理3 [4] 对于任意
和
,下列问题的全局最优解
(6)
由加权奇异值阈值(WSVT)给出
(7)
其中
是Y的SVD,并且
。
3. 加权非凸非光滑最小化问题
在这一部分中,我们利用矩阵奇异值上的
范数的非凸替代族来逼近秩函数,提出了加权非凸非光滑最小化问题,并利用迭代加权核范数(IRNN)算法对该问题进行求解。
3.1. 模型的建立
本文为了更好地逼近秩函数,将表1中的
范数的非凸替代族扩展到矩阵的奇异值上,建立了下列一般加权非凸非光滑低秩极小化模型。
(8)
其中
,
是
的第i个奇异值,s是非递减、非负的权重向量,
,g是罚函数,f是损失函数。它们分别满足以下假设:
假设1
在
上是单调递增的、连续的、凹的,并且可以是非光滑的。
假设2
是
型光滑函数,即它的梯度是Lipschitz连续的。
可以看到表1中所有
范数的非凸替代都满足假设1,因此
是秩函数的非凸替代,对于假设2中的损失函数f,最广泛使用的是
。
3.2. 模型的求解
为了符号简便,我们把X的奇异值表示为
,并且是非递增的。
表示第k次迭代的变量X,
是
的第i个奇异值,记为
。
由假设g是凹函数,根据定义3超梯度的概念,对于
,我们有
(9)
又由于奇异值是非递减且不小于0的,即
,由引理2超梯度是反单调算子,我们有
(10)
因此,我们可以解决下列松弛问题来更新
:
(11)
进一步地,我们在
处对
进行线性化,并添加一个近端项:
(12)
式中:
。结合(9)和(10),我们可以更新
通过求解下式:
(13)
因此,根据引理3,(13)的全局最优解可以由加权奇异值阈值(WSVT)给出
(14)
其中,
是Y的SVD,
。
从引理3可以看出,(13)在求解(11)的过程中起着重要的作用,并且该方法对于满足假设1的所有g都成立。如果
,那么
降到凸核范数
。在这种情况下,对于所有
,
。加权奇异值阈值(WSVT)就降为传统的奇异值阈值法(SVT) [5],这是凸低秩优化中的一个重要子程序。这时更新规则(11)降为已知的近端梯度方法 [6]。
通过解(13)更新
,我们再更新权重
。迭代更新
及其奇异值
对应的权值,得到了迭代加权核范数(IRNN)算法。IRNN的整个过程如算法1所示。如果Lipschitz常数
未知或不可计算,则可使用回溯规则在每次迭代中估计
[6]。其中,对于
惩罚,如果
,那么
。根据(11)中
的更新规则,我们得到了
,这保证了序列
的秩是非递增的。
4. 实验
在本节中,我们将本文方法应用于图像恢复,并与TNNR和DW-TNNR方法作比较。我们选取的图片大小为300 × 300 × 3,并且噪声等级设置为50%。通过对比原始图片的恢复情况,可以直观看到去噪模型的恢复效果如图1所示。同时,峰值信噪比(Peak Signal-to-Noise Ratio, PSNR)值是评价图像质量的常用标准。我们使用恢复图像的PSNR值来评估在相同噪声情况下不同方法的性能。值得注意的是,恢复图像的PSNR值越高,代表图片的恢复效果就越好,具体数据如表2所示。
Table 2. Comparison of PSNR values and time for denoising by four algorithms
表2. 四种算法去噪PSNR值和时间对比
5. 结论
本文提出并求解了一种新的加权非凸非光滑最小化问题。图像去噪的实验结果表明,在相同噪声下,该方法能够有效去噪并获得较好的视觉效果。