双加权截断核范数张量填充

Double Weighted Truncated Nuclear Norm Regularization for Low-Rank Tensor Completion

摘要: 低秩张量填充根据数据的低秩性来恢复所有丢失的元素来更好地描述高维数据结构，逐渐得到各领域学者的重视。先前的学者们已经提出了张量核范数的几种定义，但是可能无法正确地近似张量真正的秩，并且在优化中这种方法没有明确地使用低秩性质，基于此，有学者提出了张量截断核范数(T-TNN)，但需要大量的迭代才能收敛。因此，本文提出了一种新的方法双加权截断核范数张量填充(DW-T-TNN)，为张量每片分配不同的权重，以加速收敛，并获得可接受的性能。本文设计了一种简洁的梯度下降方法，代替了T-TNN第二步的迭代更新方案。在实验过程中，我们的方法有良好的视觉效果并且所用时间更少。

Abstract: To better describe the high dimensional data structure, low-rank tensor completion based on the low rank property has gradually attracted the attention of scholars in various fields whose partial elements are missing. Previous scholars have proposed several definitions of tensor nuclear norm, but it may not be able to correctly approximate the real rank of tensor, and this method does not explicitly use the low rank property in optimization. Based on this, some scholars have proposed Tensor Truncated Nuclear Norm (T-TNN), but it requires numerous iterations to converge. Therefore, this paper proposes a new method, Double Weighted Truncated Nuclear Norm Regularization for Low-Rank Tensor Completion (DW-T-TNN) which assigns different weights to each piece of tensor to accelerate convergence and obtain acceptable performance. In this paper, an efficient gradient descent strategy is designed to replace the iterative update scheme of the second step of T-TNN. In the experiment of real-world image, our method has good visual effect and takes less time.

1. 引言

近年来，随着现代网络技术的急速发展，计算机视觉、图像处理以及推荐系统等领域得到了前所未有的关注与高度，与此同时获取大量的高维数据也逐渐变得简单起来。但是获取高维数据过程中难免会有部分数据丢失的情况出现。虽然矩阵填充也可恢复出丢失的元素，但是当待恢复的高维数据具有相对复杂的结构时，利用矩阵填充可能会造成维度灾难、过拟合以至于最终破坏数据结构。因此作为矩阵填充的推广，根据数据的低秩性来恢复出所有丢失的元素来更好地描述高维数据结构的低秩张量填充，逐渐得到各领域学者的重视。

通过将彩色图像或者视频看做三维张量，先前的学者们已经提出了张量核范数的几种定义。但是这些定义可能无法正确地近似于张量真正的秩而且在优化中没有明确地使用低秩性质，这就造成了局限性。最近提出的截断核范数(TNN)被证明可以代替传统的核范数来更好的近似秩。基于此， [1] 提出了张量截断核范数(T-TNN)将截断核范数从矩阵情形推广到张量情形。但是这种方法需要多次迭代才能收敛。本文在熟悉截断核范数和张量相关知识的基础上，认真分析国内外学者在张量填充领域的研究现状，提出了双加权截断核范数张量填充(DW-T-TNN)方法，将不同的权重分别分配给张量每个前片的行和列，以加快收敛速度并获得可接受的性能。同时提出了一种简单的梯度下降方法，代替了T-TNN中第二步的迭代更新方法。在真实数据上进行的有效实验证明，DW-T-TNN具有良好的性能，在完成的速度和视觉效果上都具有优势。

2. 预备知识

定义1 [2] 张量核范数：张量 $A\in {ℝ}^{n_1\times n_2\times n_3}$ 的核范数记为 ${\Vert \mathcal{A}\Vert }_{\ast }$，表示 $\bar{\mathcal{A}}$ 所有正面切片核范数的平均值，即： ${\Vert A\Vert }_F=\frac{1}{\sqrt{n_3}}{\Vert \bar{A}\Vert }_F$

定义2 [2] 张量 $F$ 范数：张量 $A\in {ℝ}^{n_1\times n_2\times n_3}$， $\bar{A}$ 表示张量进行傅里叶变换之后的块循环矩阵，张量 $F$ 范数即： ${\Vert A\Vert }_F=\frac{1}{\sqrt{n_3}}{\Vert \bar{A}\Vert }_F$

定义3 [1] 张量截断核范数：

张量 $X\in {ℝ}^{n_1\times n_2\times n_3}$ 的截断核范数为 ${\Vert X\Vert }_r$，被定义为

${\Vert X\Vert }_r={\Vert X\Vert }_{\ast }-\underset{\begin{array}{l}A{A}^{\text{T}}=I\\ B{B}^{\text{T}}=I\end{array}}{\max }tr\left(A\ast X\ast B\right)$

其中 $A\in {ℝ}^{n_1\times n_2\times n_3}$， $B\in {ℝ}^{n_1\times n_2\times n_3}$ 是由TSVD生成的，

定义4 [3] 张量奇异值分解：

设 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ 的TSVD是 $A=U\ast S\ast V^{\text{T}}$，其中 $U\in {ℝ}^{n_1\times n_1\times n_3}$ $V\in {ℝ}^{n_2\times n_2\times n_3}$ 是正交的， $S\in {ℝ}^{n_1\times n_2\times n_3}$ 是f-对角张量。

定义5 [2] $A\in {ℝ}^{n_1\times n_2\times n_3}$， $B\in {ℝ}^{n_1\times n_2\times n_3}$，则有 $\langle A,B\rangle =\frac{1}{n_3}\langle \bar{A},\bar{B}\rangle$。

3. 双加权截断核范数张量填充

3.1. 模型的建立

由 [1] 易证明，张量截断核范数等价于

$\begin{array}{l}\min \underset{A{A}^{\text{T}}=B{B}^{\text{T}}=I}{\max tr\left(A\ast X\ast B^{\text{T}}\right)}-\underset{C{C}^{\text{T}}=D{D}^{\text{T}}=I}{\max tr\left(C\ast X\ast D^{\text{T}}\right)}\\ \text{st}{X}_{\Omega }=M_{\Omega }\end{array}$ (1)

其中 $A\in {ℝ}^{n_1\times n_1\times n_3}$， $B\in {ℝ}^{n_1\times n_2\times n_3}$， $C\in {ℝ}^{n_1\times r\times n_3}$， $D\in {ℝ}^{n_2\times r\times n_3}$

显而易见，直接求解上式并不容易，所以我们把这个优化分为两步进行，指定 $X_1=M_{\Omega }$ 作为初始化.在第k次迭代中，第一步我们固定 $X_k$ 来更新 $A_k$ 、 $B_k$ 、 $C_k$ 和 $D_k$。

$A_K=U^{\text{T}}$ (2)

$B_K=V{\left(:,1:n_1,:\right)}^{\text{T}}$ (3)

$C_K=U{\left(:,1:r,:\right)}^{\text{T}}$ (4)

$D_K=V{\left(:,1:r,:\right)}^{\text{T}}$ (5)

接下来在第二步中，我们通过保持其他变量不变，通过下列算式更新优化 $X_{K+1}$。

$\begin{array}{l}\min \underset{A{A}^{\text{T}}=B{B}^{\text{T}}=I}{tr\left(A_k\ast X\ast B_k^{\text{T}}\right)}-\underset{C{C}^{\text{T}}=D{D}^{\text{T}}=I}{tr\left(C_k\ast X\ast D_k^{\text{T}}\right)}\\ \text{st}{X}_{\Omega }=M_{\Omega }\end{array}$ (6)

然后引入辅助变量，在这里我们采用交替乘子法进行求解，

$\begin{array}{l}\min \underset{A{A}^{\text{T}}=B{B}^{\text{T}}=I}{tr\left(A_k\ast X\ast B_k^{\text{T}}\right)}-\underset{C{C}^{\text{T}}=D{D}^{\text{T}}=I}{tr\left(C_k\ast X\ast D_k^{\text{T}}\right)}\\ \text{st}{X}_{\Omega }=W_{\Omega }{W}_{\Omega }=M_W\end{array}$ (7)

随后转化成为一个无约束的增广拉格朗日函数进行求解，

$L\left(X,W,Y\right)=tr\left(A_k\ast X\ast B_k^{\text{T}}\right)-tr\left(C_k\ast X\ast D_k^{\text{T}}\right)+\frac{\mu }{2}{\Vert X-W\Vert }_F^2+tr\left(Y^{{}^{\text{T}}}\left(X-W\right)\right)$ (8)

为了更准确，有更高优先级的进行填充，我们选择在这里加入权重

$L\left(X,W,Y\right)=tr\left(A_k\ast X\ast B_k^{\text{T}}\right)-tr\left(C_k\ast X\ast D_k^{\text{T}}\right)+\frac{\mu }{2}{\Vert P\left(X-W\right)Q\Vert }_F^2+tr\left(Y^{{}^{\text{T}}}P\left(X-W\right)Q\right)$ (9)

其中 $P$， $Q$ 是权重对角张量。

3.2. 模型的优化

假设 $X_K$， $Y_K$ 表示第二步中第K次迭代的结果，我们通过保持其他变量不变，来更新 $W_{K+1}$ 如下

$\begin{array}{c}{W}_{K+1}=\arg \min L\left(X,W,Y\right)\\ =\underset{W}{\arg \min }-tr\left(C_k\ast W\ast D_k^{\text{T}}\right)+\frac{\mu }{2}{\Vert P\left(X-W\right)Q\Vert }_F^2+tr\left(Y^{{}^{\text{T}}}P\left(X-W\right)Q\right)\\ =X_K+\frac{1}{\mu }\left(P^{-2}{C}_K^{\text{T}}{D}_k{Q}^{-2}+P^{-1}{Y}_K{Q}^{-1}\right)\end{array}$ (10)

由约束条件可知，观测元素的值保持不变，在此获得

$W_{K+1}={\left(W_{K+1}\right)}_{{\Omega }^c}+M_{\Omega }$ (11)

$X$ 的更新如下

$\begin{array}{c}{X}_{k+1}=\underset{X}{\arg \min }L\left(X,W_{K+1},Y_K\right)\\ =\underset{X}{\arg \min }tr\left(A_k\ast X\ast B_k^{\text{T}}\right)+\frac{{\mu }_K}{2}{\Vert P\left(X-W_{K+1}\right)Q+\frac{Y_K}{{\mu }_K}\Vert }_F^2\\ =W_{K+1}-\frac{1}{{\mu }_K}\left(P^{-2}{A}_K^{\text{T}}{B}_k{Q}^{-2}+P^{-1}{Y}_K{Q}^{-1}\right)\end{array}$ (12)

$Y$ 的更新如下

$Y_{k+1}=Y_k+{\beta }_{k}P\left(X_{k+1}-W_{K+1}\right)Q$ (13)

其中 ${\beta }_k$ 是单调递增序列。

这三项更新步骤在实际应用中需要大量的迭代才能收敛，计算代价很大。在此我们根据其中的内在关联，推出一种简洁的梯度下降方式，即在不需要大量迭代步骤的情况下，就可以有效地更新 $X$，如下定理1所示。

定理1 [4]：如果 $0<{\mu }_t<{\mu }_{t+1}$， $\forall t=1,2,\cdots ,N$， $\frac{1}{{\alpha }_K}={\displaystyle \underset{t=1}{\overset{N-1}{\sum }}\frac{1}{{\mu }_t}}$，由(10)~(13)， $X_k$ 的更新可以由下的面一步迭代更新完成

$X=X_k-\frac{1}{{\alpha }_K}{P}^{-2}\left(A_K^{\text{T}}{B}_K-C_K^{\text{T}}{D}_K\right)Q^{-2}$ (14)

$X_{k+1}={\left(X\right)}_{{\Omega }^C}+M_{\Omega }$ (15)

其中 $\frac{1}{{\alpha }_K}$ 代表补步长，证明在此处不详述。

此外，为了简便表示，下面我们定义两个两个对角张量 $P^{-2}=\tilde{P}$， $Q^{-2}=\tilde{Q}$，

$\tilde{P}$ 的每一个前片 ${\tilde{P}}^{\left(i\right)}=diag\left(p_1,\cdots ,p_{n_1}\right),i=1,\cdots ,n_3$ (16)

$\tilde{Q}$ 的每一个前片 ${\tilde{Q}}^{\left(i\right)}=diag\left(q_1,\cdots ,q_{n_2}\right),i=1,\cdots ,n_3$ (17)

${\left\{p_i\right\}}_{i=1}^{n_1}\ge 0$， ${\left\{q_i\right\}}_{i=1}^{n_2}\ge 0$ 分别根据每行和每列中观察到的元素的数量精确确定，如下

$\begin{array}{l}{p}_i=\exp \left(-{\theta }_1\left(\frac{N_i^r}{n}-1\right)\right)-1,i=1,\cdots ,n_1\\ q_i=\exp \left(-{\theta }_2\left(\frac{N_j^c}{m}-1\right)\right)-1,j=1,\cdots ,n_2\end{array}$ (18)

其中 ${\theta }_1$ 和 ${\theta }_2$ 是缩放权重，这意味着具有更多的观察元素的行(列)具有更小的权重值，并且 $p_i=0\left(q_i=0\right)$ 意味着此时没有元素丢失。

基于上述，我们引入梯度下降法。

首先我们介绍一个引理 [5]：假设对于任意两个张量 $A\in {ℝ}^{n_1\times n_2\times n_3}$， $B\in {ℝ}^{n_2\times n_4\times n_3}$，令 $F=A\ast B$，则有下面性质成立

1) ${\Vert A\Vert }_F^2=\frac{1}{n_3}{\Vert \bar{A}\Vert }_F^2$。

2) $F=A\ast B$ 和 $\bar{F}=\bar{A}*\bar{B}$ 相互相等。

${\bar{A}}_k^{\left(i\right)}=U_K^{\left(1\right)\text{T}}={\left[u_1,\cdots ,u_r,\cdots ,u_{n_1}\right]}^{\text{T}}={\left[C_K^{\text{T}},u_{r+1},\cdots ,u_{n_1}\right]}^{\text{T}}={\left[C_K^{\text{T}},H_k^{\text{T}}\right]}^{\text{T}},i=1,2,\cdots ,n_3$ (19)

${\bar{B}}_k^{\left(i\right)}={\left[v_1,\cdots ,v_r,\cdots ,v_{n_1}\right]}^{\text{T}}={\left[D_K^{\text{T}},v_{r+1},\cdots ,v_{n_1}\right]}^{\text{T}}={\left[D_K^{\text{T}},L_k^{\text{T}}\right]}^{\text{T}},i=1,2,\cdots ,n_3$ (20)

由引理1， $A^{\text{T}}\ast B=\overline{A^{\text{T}}}*\bar{B}$，容易证得

$A_K^{\text{T}}{B}_K-C_K^{\text{T}}{D}_K=\left[{\bar{C}}_K^{\text{T}},{\bar{H}}_K^{\text{T}}\right]\left[\begin{array}{c}{\bar{D}}_K\\ {\bar{L}}_K\end{array}\right]={\bar{H}}_K^{\text{T}}{\bar{L}}_K=H_K^{\text{T}}{L}_K,i=1,2,\cdots ,n_3$ (21)

因此，通过定理1，(16)~(18)，和(21)， $X_{K+1}$ 可以不用大量迭代，即通过一个简单的梯度下降方法就可以有效地计算，即：

$X^{*}=X_k-\frac{1}{{\alpha }_K}P{H}_K^{\text{T}}{L}_{K}Q$ (22)

$X_{k+1}={\left(X^{*}\right)}_{{\Omega }^C}+M_{\Omega }$ (23)

在上面两个式子的基础上，我们发现它们等价于函数 $tr\left(H_k\tilde{P}X\tilde{Q}{L}_k^{\text{T}}\right)$ 的梯度下降法搜索的解。

由于上述一步梯度下降法的优点，代替了在第二步中迭代计算 $X_k$，因此，我们可以将(1)转换为以下公式：

$\begin{array}{l}\min tr\left(H\tilde{P}X\tilde{Q}{L}^{\text{T}}\right)\\ s.t.X_{\Omega }=M_{\Omega }\end{array}$ (24)

注意到当 $r=n_1$ 意味着 $H=O$， $L=O$ 这就意味着梯度消失，所以在此我们选择 $r\ll n_1$ 这样就会避免这种情况的发生，这也符合视觉数据(例如真实图像)普遍具有低阶结构的事实。换句话说，实际的秩r要比图像的尺寸小得多。

初始值 $X_1=M_{\Omega }$，(24)的优化是通过一个梯度下降法解决如下

$X_{k+1}=X_k-\frac{1}{{\alpha }_K}\tilde{P}{H}_K^{\text{T}}{L}_K\tilde{Q}$ (25)

$X_{k+1}={\left(X_{k+1}\right)}_{{\Omega }^C}+M_{\Omega }$

其中 $\frac{1}{{\alpha }_K}$ 是递减的步长，满足

${\alpha }_{K+1}=\rho {\alpha }_K$ (26)

其中 $\rho >1$ 是一个常数。

4. 实验部分

实验部分将本文模型(DW-T-TNN)与TNN (截断核范数)、T-TNN (张量截断核范数)、DW-TNN (加权截断核范数)这3个模型来作比较，在此选取图片大小为300 × 300 × 3，椒盐噪声为50%的彩色图片。我们通过对比彩色图片的恢复情况的视觉效果，展示本文模型的恢复效果。下面列出在单张彩色图片上这四种模型恢复上的视觉效果，如图1所示。并且对比了四种模型恢复图片所用的时间，如表1所示。

原始图片 噪声图片 DW-T-TNN DW-TNN T-TNN TNN

Figure 1. Comparison of visual effects of four different denoising algorithms (a) Original image; (b) Noisy image; (c) DW-T- TNN; (d) DW-TNN; (e) T-TNN; (f) TNN

图1. 四种不同算法去噪视觉效果对比 (a) 原始图片；(b) 噪声图片；(c) DW-T-TNN；(d) DW-TNN；(e) T-TNN；(f) TNN

Table 1. Comparison of denoising time of four different algorithms

表1. 四种不同算法去噪时间对比

5. 结论

在本文中，我们提出了双加权截断核范数张量填充模型，以及一种简洁的梯度下降方法。实验表明在相同噪声情况下，视觉效果和时间都优于其他算法，所以该方法对图像恢复是有优化效果的。

参考文献