加权非凸非光滑低秩矩阵填充

Weighted Nonconvex Nonsmooth Low-Rank Matrix Completion

摘要: 本文利用矩阵奇异值上的l₀范数的非凸替代族来逼近秩函数，提出一种新的加权非凸非光滑最小化问题，并使用迭代加权核范数(IRNN)算法来求解该问题。实验结果表明，该方法能够很好地处理非凸非光滑问题，实现图像去噪。

Abstract: In this paper, we propose a new weighted nonconvex nonsmooth minimization problem and use Iteratively Reweighted Nuclear Norm (IRNN) algorithm to solve the problem. It is worth mentioning that we use the nonconvex substitution family of l₀-norm on the singular value of the matrix to approximate the rank function. Experimental results show that this method can deal with nonconvex nonsmooth problems well and realize image denoising.

1. 引言

低秩矩阵逼近是一种从退化的观测中恢复低秩矩阵的方法，近年来受到了计算机视觉和机器学习界的广泛关注，并已经成功应用于各个领域，如矩阵填充、背景建模和运动分割等。

众所周知，秩极小化问题很难求解。因此，秩函数通常由凸核范数代替，这类凸问题可以由许多已知的求解器 [1] [2] [3] 有效地求解。然而，核范数是秩函数的松散近似，由核范数近似秩函数得到的解通常是次优的。为了更好地逼近秩函数，本文利用矩阵奇异值上的 ${\mathcal{l}}_0$ 范数的非凸替代族来逼近秩函数，从而提出了一种新的加权非凸非光滑最小化问题，并使用迭代加权核范数(IRNN)算法对该问题进行求解。

2. 预备知识

在这一节中，我们介绍了Lipschitz连续的定义，并引入了超梯度的概念，它将在求解非凸非光滑问题中使用。我们知道，次梯度是凸函数在非光滑点的梯度的扩展，实际上超梯度则是凹函数在非光滑点的梯度的扩展。

定义1 (Lipschitz连续)称f的梯度 $\nabla f$ 为Lipschitz连续，如果对于任意 $X,Y\in {ℝ}^{m\times n},L\left(f\right)>0$，有

${\Vert \nabla f\left(X\right)-\nabla f\left(Y\right)\Vert }_F\le L\left(f\right){\Vert X-Y\Vert }_F$ (1)

称 $L\left(f\right)$ 为 $\nabla f$ 的Lipschitz常数。

定义2 (次梯度)若g是凸的、非光滑的，则其在x处的次梯度为u，则下列不等式成立

$g\left(x\right)+\langle u,y-x\rangle \le g\left(y\right)$ (2)

定义3 (超梯度)设g是凹的，向量v是g在x点的超梯度，如果对于每一个y，有下面的不等式成立

$g\left(x\right)+\langle v,y-x\rangle \ge g\left(y\right)$ (3)

非光滑点处的超梯度可能不是唯一的，g在x处的所有超梯度称为g在x处的超微分，并表示为 $\partial g\left(x\right)$。如果g在x处可微，那么 $\nabla g\left(x\right)$ 是唯一的超梯度，即 $\partial g\left(x\right)=\left\{\nabla g\left(x\right)\right\}$。一些常见凹函数的超梯度如表1所示。

Table 1. Popular nonconvex surrogate functions and their supergradients

表1. 常见的非凸替代函数和它们的超梯度

对于凹函数 $g,-g$ 是凸的，反之亦然。根据这一事实，g的超梯度与 $-g$ 的次梯度之间存在以下关系。

引理1 设 $g\left(x\right)$ 是凹的， $h\left(x\right)=-g\left(x\right)$。对于任何 $v\in \partial g\left(x\right)$， $u=-v\in -\partial h\left(x\right)$ 成立，反之亦然。

引理1给出了超梯度与次梯度的关系，从而得到了超梯度的一些性质。众所周知，对于任何 $u_1\in \partial h\left(x\right)$， $u_2\in \partial h\left(y\right)$，凸函数h的次微分称为单调算子，即

$\langle u_1-u_2,x-y\rangle \ge 0$ (4)

凹函数的超微分则具有如下相反的性质。

引理2 对于任何 $v_1\in \partial g\left(x\right)$， $v_2\in \partial g\left(y\right)$，凹函数g的超微分称为反单调算子，即

$\langle v_1-v_2,x-y\rangle \le 0$ (5)

根据引理2，假设 $g\left(x\right)$ 是凹的。如果 $x\le y$，那么对于任意 $v_1\in \partial g\left(x\right)$ 和 $v_2\in \partial g\left(y\right)$ 都有 $v_1\ge v_2$。

引理3 [4] 对于任意 $\lambda >0,Y\in {ℝ}^{m\text{×}n}$ 和 $0\le w_1\le w_2\le \cdots \le w_s$ $\left(s=\min \left(m,n\right)\right)$，下列问题的全局最优解

$\min \lambda {\displaystyle \underset{i=1}{\overset{s}{\sum }}{w}_i}{\sigma }_i\left(X\right)+\frac{1}{2}{\Vert X-Y\Vert }_F^2$ (6)

由加权奇异值阈值(WSVT)给出

$X^{*}=U{S}_{\lambda w}\left(\Sigma \right)V^{\text{T}}$ (7)

其中 $Y=U\Sigma V^{\text{T}}$ 是Y的SVD，并且 $S_{\lambda w}\left(\Sigma \right)=\text{Diag}\left\{{\left({\Sigma }_{ii}-\lambda w_i\right)}_{+}\right\}$。

3. 加权非凸非光滑最小化问题

在这一部分中，我们利用矩阵奇异值上的 ${\mathcal{l}}_0$ 范数的非凸替代族来逼近秩函数，提出了加权非凸非光滑最小化问题，并利用迭代加权核范数(IRNN)算法对该问题进行求解。

3.1. 模型的建立

本文为了更好地逼近秩函数，将表1中的 ${\mathcal{l}}_0$ 范数的非凸替代族扩展到矩阵的奇异值上，建立了下列一般加权非凸非光滑低秩极小化模型。

$\underset{X\in {ℝ}^{m\text{×}n}}{\text{min}}F\left(x\right)={\displaystyle \underset{i=1}{\overset{m}{\sum }}{s}_{i}g\left({\sigma }_i\left(X\right)\right)}+f\left(X\right)$ (8)

其中 $m\ll n$， ${\sigma }_i\left(X\right)$ 是 $X\in {ℝ}^{m\text{×}n}$ 的第i个奇异值，s是非递减、非负的权重向量， $s=sort\left(\left(\max \left(\sigma -1,0\right)+1\right)/\left(\max \left(\sigma +1,0\right)+1\right)\right)$，g是罚函数，f是损失函数。它们分别满足以下假设：

假设1 $g:{ℝ}^{+}\to {ℝ}^{+}$ 在 $\left[0,\infty \right)$ 上是单调递增的、连续的、凹的，并且可以是非光滑的。

假设2 $f:{ℝ}^{m\times n}\to {ℝ}^{+}$ 是 $C^{1,1}$ 型光滑函数，即它的梯度是Lipschitz连续的。

可以看到表1中所有 ${\mathcal{l}}_0$ 范数的非凸替代都满足假设1，因此 ${\displaystyle \underset{i=1}{\overset{m}{\sum }}g\left({\sigma }_i\left(X\right)\right)}$ 是秩函数的非凸替代，对于假设2中的损失函数f，最广泛使用的是 $\frac{1}{2}{\Vert X-Y\Vert }_F^2$。

3.2. 模型的求解

为了符号简便，我们把X的奇异值表示为 ${\sigma }_1,{\sigma }_2,\cdots ,{\sigma }_m$，并且是非递增的。 $X^k$ 表示第k次迭代的变量X， ${\sigma }_i\left(X^k\right)$ 是 $X^k$ 的第i个奇异值，记为 ${\sigma }_i^k$。

由假设g是凹函数，根据定义3超梯度的概念，对于 $w_i^k\in \partial g\left({\sigma }_i^k\right)$，我们有

$g\left({\sigma }_i\right)\le g\left({\sigma }_i^k\right)+w_i^k\left({\sigma }_i-{\sigma }_i^k\right)$ (9)

又由于奇异值是非递减且不小于0的，即 ${\sigma }_1^k\ge {\sigma }_2^k\ge \cdots \ge {\sigma }_m^k\ge 0$，由引理2超梯度是反单调算子，我们有

$0\le w_1^k\le w_2^k\le \cdots \le w_m^k$ (10)

因此，我们可以解决下列松弛问题来更新 $X^{k+1}$ ：

$\begin{array}{c}{X}^{k+1}=\arg \underset{X}{\min }{\displaystyle \underset{i=1}{\overset{m}{\sum }}{s}_{i}g\left({\sigma }_i^k\right)}+s_i{w}_i^k\left({\sigma }_i-{\sigma }_i^k\right)+f\left(X\right)\\ =\arg \underset{X}{\min }{\displaystyle \underset{i=1}{\overset{m}{\sum }}{s}_i{w}_i^k}{\sigma }_i+f\left(X\right)\end{array}$ (11)

进一步地，我们在 $X^k$ 处对 $f\left(X\right)$ 进行线性化，并添加一个近端项：

$f\left(X\right)\approx f\left(X^k\right)+\langle \nabla f\left(X^k\right),X-X^k\rangle +\frac{\mu }{2}{\Vert X-X^k\Vert }_F^2$ (12)

式中： $\mu >L\left(f\right)$。结合(9)和(10)，我们可以更新 $X^{k+1}$ 通过求解下式：

$\begin{array}{c}{X}^{k+1}=\arg \underset{X}{\min }{\displaystyle \underset{i=1}{\overset{m}{\sum }}{s}_{i}g\left({\sigma }_i^k\right)}+s_i{w}_i^k\left({\sigma }_i-{\sigma }_i^k\right)\\ +f\left(X^k\right)+\langle \nabla f\left(X^k\right),X-X^k\rangle +\frac{\mu }{2}{\Vert X-X^k\Vert }_F^2\\ =\arg \underset{X}{\min }{\displaystyle \underset{i=1}{\overset{m}{\sum }}{s}_i{w}_i^k{\sigma }_i}+\frac{\mu }{2}{\Vert X-\left(X^k-\frac{1}{\mu }\nabla f\left(X^k\right)\right)\Vert }_F^2\\ =\arg \underset{X}{\min }\frac{1}{\mu }{\displaystyle \underset{i=1}{\overset{m}{\sum }}{s}_i{w}_i^k{\sigma }_i}+\frac{1}{2}{\Vert X-\left(X^k-\frac{1}{\mu }\nabla f\left(X^k\right)\right)\Vert }_F^2\end{array}$ (13)

因此，根据引理3，(13)的全局最优解可以由加权奇异值阈值(WSVT)给出

$X^{*}=U{S}_{sw/\mu }\left(\Sigma \right)V^{\text{T}}$ (14)

其中， $Y=U\Sigma V^{\text{T}}$ 是Y的SVD， $S_{sw/\mu }\left(\Sigma \right)=\text{Diag}\left\{{\left({\Sigma }_{ii}-sw/\mu \right)}_{+}\right\}$。

从引理3可以看出，(13)在求解(11)的过程中起着重要的作用，并且该方法对于满足假设1的所有g都成立。如果 $g\left(x\right)=x$，那么 ${\displaystyle \underset{i=1}{\overset{m}{\sum }}g\left({\sigma }_i\right)}$ 降到凸核范数 ${\Vert X\Vert }_{*}$。在这种情况下，对于所有 $i=1,\cdots ,m$， $w_i^k=1$。加权奇异值阈值(WSVT)就降为传统的奇异值阈值法(SVT) [5]，这是凸低秩优化中的一个重要子程序。这时更新规则(11)降为已知的近端梯度方法 [6]。

通过解(13)更新 $X^{k+1}$，我们再更新权重 $w_i^{k+1}\in \partial g\left({\sigma }_i\left(X^{k+1}\right)\right),i=1,2,\cdots ,m$。迭代更新 $X^{k+1}$ 及其奇异值

对应的权值，得到了迭代加权核范数(IRNN)算法。IRNN的整个过程如算法1所示。如果Lipschitz常数

$L\left(f\right)$ 未知或不可计算，则可使用回溯规则在每次迭代中估计 $\mu$ [6]。其中，对于 $L_p$ 惩罚，如果 ${\sigma }_i^k=0$，那么 $w_i^k\in \partial g\left({\sigma }_i^k\right),i=\left\{+\infty \right\}$。根据(11)中 $X^{k+1}$ 的更新规则，我们得到了 ${\sigma }_i^{k+1}=0$，这保证了序列 $\left\{X^k\right\}$ 的秩是非递增的。

4. 实验

在本节中，我们将本文方法应用于图像恢复，并与TNNR和DW-TNNR方法作比较。我们选取的图片大小为300 × 300 × 3，并且噪声等级设置为50%。通过对比原始图片的恢复情况，可以直观看到去噪模型的恢复效果如图1所示。同时，峰值信噪比(Peak Signal-to-Noise Ratio, PSNR)值是评价图像质量的常用标准。我们使用恢复图像的PSNR值来评估在相同噪声情况下不同方法的性能。值得注意的是，恢复图像的PSNR值越高，代表图片的恢复效果就越好，具体数据如表2所示。

(a) (b) (c) (d) (e)

Figure 1. Comparison of image restoration results of different methods: (a) Original images; (b) Adding 50% noise images; (c) IRNN; (d) TNNR-APGL; (e) DW-TNNR

图1. 不同方法图像恢复结果对比：(a) 原始图片；(b) 添加50%噪声图片；(c) IRNN；(d) TNNR-APGL；(e) DW-TNNR

Table 2. Comparison of PSNR values and time for denoising by four algorithms

表2. 四种算法去噪PSNR值和时间对比

5. 结论

本文提出并求解了一种新的加权非凸非光滑最小化问题。图像去噪的实验结果表明，在相同噪声下，该方法能够有效去噪并获得较好的视觉效果。