双因子张量范数正则化低秩张量填充

Double Factor Tensor Norm Regularized Low Rank Tensor Completion

摘要: 本文提出了一种新的正则化方法，解决了低秩张量恢复问题。通过将张量Schatten-p范数分解成l_2,q范数与l_2,1范数的加权和，避免了求解张量Schatten-p范数需要张量奇异值分解的问题，从而降低了算法的复杂度。采用交替方向乘子法用于求解提出的模型。通过真实数据的实验，在精度和时间复杂度两个方面验证了算法的有效性。

Abstract: In this paper, a new regularization method is proposed to solve the recovery problem of low rank tensors. By decomposing the tensor Schatten-p norm into the weighted sum of l_2,q -norm and l_2,1 -norm, the problem of solving the tensor Schatten-p norm requiring tensor singular value decom-position is avoided, reducing the complexity of the algorithm. The alternating direction multiplier method is used to solve the proposed model. Experiments on real data demonstrate the effective-ness of the algorithm in terms of accuracy and time complexity.

1. 引言

随着信息技术的迅速发展和应用，数据填充已经成为了计算机视觉、人工智能和优化领域研究的热点问题。数据可以用矩阵来表示，而张量是矩阵向更高维度的推广，可以更大程度上保留数据结构的完整性。在实际场景中，由于传感器的故障，不当的人类操作和遮挡等，计算机视觉应用中遇到的张量数据很少是完整的。由此，恢复高质量的张量数据对于一些实际应用是必不可少的。为了弥合现实与需求之间的差异，需要从受损或不完整的张量数据中恢复完整的信息。以张量为代表的多媒体数据，如彩色图像和视频，由于空间相关性、全局对称性和局部相似性等原因，通常表现出低秩性。低秩张量恢复的一个典型问题是低秩张量填充问题，即估计张量中的缺失值。这是计算机科学和数学领域的一个持续的研究挑战。广泛应用于许多现实问题，如视觉数据 [1] [2]、EEG数据 [3] [4]、高光谱数据分析 [5]、链接预测 [6]。但秩的极小化问题很难求解，根据张量定义的秩的不同，张量分解方式也有不同，如基于CP分解 [7] 的CANDECOMP/PARAFAC秩，基于Tucker分解 [8] 的Tucker秩，基于TT分解 [9] 的Tensor Train秩，以及基于张量奇异值分解 [10] 的tubal秩。因此张量秩的替代有很多种，但是很多方法有其局限性，寻找复杂度低的张量填充模型极其重要。

本文主要研究张量奇异值框架下的三阶张量填充问题，在过去的几年中，我们见证了许多方法的发展，秩最小化方法可分为两类。一种是低秩张量因子分解方法，另一种是张量核范数最小化方法。低秩张量因子分解方法旨在将给定张量分解成两个较小的张量，可以在某些损失函数下重建张量，但是却忽略了目标函数中谱正则化的使用。张量核范数最小化方法代表了研究的另一个主要分支，它的一个限制是过度惩罚奇异值的大条目，大规模张量的奇异值分解导致了较高的计算成本，研究人员试图用一些非凸范数来代替核范数。最近研究表明，利用非凸的 ${\mathcal{l}}_p$ 范数来松弛 ${\mathcal{l}}_0$ 范数(向量的非零条目数) [11] [12] 和Schatten-p范数，以近似秩函数有最佳的性能 [13] [14]，而不是 ${\mathcal{l}}_1$ 范数和核范数作为压缩感知和矩阵恢复问题的替代。对于张量数据，Liu等人 [15] 基于张量奇异值分解定义了张量p收缩核范数，这对于矩阵情况下的高维大规模数据来说是昂贵的。为了解决Schatten-p范数最小化的高计算成本，Kong等人 [16] 定义了低秩张量补全的张量Schatten-p拟范数( $0<p<1$ )，并提供了一个multi-tensor-Schatten-p拟范数替代项，以转换一个非凸和非光滑的大型张量Schatten-p范数，对于 $p>0$ 的多个小尺度因子张量的总和，Schatten-p可以是凸的和光滑的。该方法在一定程度上降低了算法的时间复杂度。然而这些形式的一个主要缺点是，需要计算多个小尺度因子张量的奇异值，会在大数据设置中限制计算。Fan [17] 等人和Jia [18] 采用矩阵因子分解的方式将Schatten-p范数分解为 ${\mathcal{l}}_{2,p}$ 范数和 ${\mathcal{l}}_{2,1}$ 范数加权和的形式，此方法不需要奇异值分解，降低了复杂度。

2. 预备知识

定义1 [19] 张量Frobenius范数：张量 $\mathcal{X}\in {ℝ}^{n_1\times n_2\times n_3}$， $\bar{X}$ 表示张量进行傅里叶变换的块对角矩阵，张量Frobenius范数为：

${\Vert \mathcal{X}\Vert }_F=\frac{1}{\sqrt{n_3}}{\Vert \bar{X}\Vert }_F$

定义2张量 ${\mathcal{l}}_{2,q}$ 范数：设 $\mathcal{X}\in {ℝ}^{n_1\times n_2\times n_3}$，则张量 ${\mathcal{l}}_{2,q}$ 范数的q次幂为：

${\Vert \mathcal{X}\Vert }_{2,q}^q=\frac{1}{n_3}{\Vert \bar{X}\Vert }_{2,q}^q$

定义3 [20] 张量奇异值分解：设 $\mathcal{X}\in {ℝ}^{n_1\times n_2\times n_3}$，则 $\mathcal{X}$ 的奇异值分解为 $\mathcal{X}=\mathcal{U}\ast \mathcal{S}\ast {\mathcal{V}}^{\text{T}}$，其中 $\mathcal{U}\ast {\mathcal{U}}^{\text{T}}=\mathcal{I}$， $\mathcal{V}\ast {\mathcal{V}}^{\text{T}}=\mathcal{I}$， $\mathcal{S}\in {ℝ}^{n_2\times n_2\times n_3}$ 是对角张量。

定义4 [16] 张量Schatten-p范数：设 $\mathcal{X}\in {ℝ}^{n_1\times n_2\times n_3}$，张量 $\mathcal{X}$ 的奇异值分解为 $\mathcal{X}=\mathcal{U}\ast \mathcal{S}\ast {\mathcal{V}}^{\text{T}}$，如果 $r={\text{rank}}_{\text{t}}\left(\mathcal{X}\right)$，则具有p次幂的t-Schatten-p范数定义为：

${\Vert \mathcal{X}\Vert }_{S_P}^p={\displaystyle \underset{i=1}{\overset{r}{\sum }}{\mathcal{S}}^p\left(i,i,1\right)}$

定理1 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$， $\mathcal{B}\in {ℝ}^{n_4\times n_2\times n_3}$，让 $\mathcal{X}=\mathcal{A}\ast {\mathcal{B}}^{\text{T}}$，则以下情况成立：

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

2) $\mathcal{X}=\mathcal{A}\ast {\mathcal{B}}^{\text{T}}$ 和 $\bar{X}=\bar{A}\ast {\bar{B}}^{\text{T}}$ 互相等价。

3. 双因子张量范数的正则化低秩张量填充

3.1. 模型确立

在本节中，为提高低秩张量模型对受损图像和视频的恢复效果，引入了一种基于tubal秩的新的张量补全的方法，将张量Schatten-p范数的形式引入传统张量补全模型。

设 $\mathcal{T}\in {ℝ}^{n_1\times n_2\times n_3}$，观察元素的位置由 $\Omega \in {\left\{0,1\right\}}^{n_1\times n_2\times n_3}$ 决定，其中如果观察到 ${\mathcal{T}}_{ijk}$，则 ${\Omega }_{ijk}=1$，否则为0。假设部分观察的数量足够大。则低tubal秩张量补全问题如下表示：

$\underset{\mathcal{X}}{\min }\frac{1}{2}{\Vert {\mathcal{P}}_{\Omega }\left(\mathcal{X}-\mathcal{T}\right)\Vert }_F^2+\lambda {\Vert \mathcal{X}\Vert }_{S_P}^p$ (1)

为了解决大规模张量Schatten-p范数最小化的高计算成本，提出了张量Schatten-p范数的因子分解形式。

定理2张量 $\mathcal{X}$ 分解为张量积形式 $\mathcal{X}=\mathcal{U}\ast {\mathcal{V}}^{\text{T}}$， $\mathcal{U}\in {ℝ}^{n_1\times d\times n_3}$， $\mathcal{V}\in {ℝ}^{n_1\times d\times n_3}$， $ran{k}_t\left(\mathcal{X}\right)=r\le d$， $q=\frac{p}{1-p}$，所以有

${\Vert \mathcal{X}\Vert }_{S_P}^p=\underset{\mathcal{X}=\mathcal{U}\ast {\mathcal{V}}^{\text{T}}}{\min }\frac{p}{q}{\Vert \mathcal{U}\Vert }_{2,q}^q+p{\Vert \mathcal{V}\Vert }_{2,1}$ (2)

应用定理2张量最优化问题模型如下：

$\underset{\mathcal{U},\mathcal{V}}{\min }\frac{1}{2}{\Vert {\mathcal{P}}_{\Omega }\left(\mathcal{X}-\mathcal{T}\right)\Vert }_F^2+\alpha {\Vert \mathcal{U}\Vert }_{2,q}^q+\beta {\Vert \mathcal{V}\Vert }_{2,1}\text{s}\text{.t}.\mathcal{X}=\mathcal{U}\ast {\mathcal{V}}^{\text{T}}$ (3)

其中 $\alpha =\frac{\lambda p}{q}$， $\beta =\lambda p$， $\mathcal{X}\in {ℝ}^{n_1\times n_2\times n_3}$， $\mathcal{U}\in {ℝ}^{n_1\times d\times n_3}$ 和 $\mathcal{V}\in {ℝ}^{n_1\times d\times n_3}$。

接下来我们用ADMM法进行求解，首先我们写出上式的拉格朗日函数。

${\mathcal{L}}_{\mu }\left(\mathcal{X},\mathcal{U},\mathcal{V},\mathcal{Y}\right)=\frac{1}{2}{\Vert {\mathcal{P}}_{\Omega }\left(\mathcal{X}-\mathcal{T}\right)\Vert }_F^2+\alpha {\Vert \mathcal{U}\Vert }_{2,q}^q+\beta {\Vert \mathcal{V}\Vert }_{2,1}+\langle \mathcal{Y},\mathcal{X}-\mathcal{U}\ast {\mathcal{V}}^{\text{T}}\rangle +\frac{\mu }{2}{\Vert \mathcal{X}-\mathcal{U}\ast {\mathcal{V}}^{\text{T}}\Vert }_F^2$ (4)

其中是 $\mathcal{Y}$ 拉格朗日乘子， $\mu$ 是拉格朗日惩罚参数， $\langle \cdot ,\cdot \rangle$ 表示张量内积算子。

3.2. 模型求解

我们用交替方向乘子法对 $\mathcal{X},\mathcal{U},\mathcal{V}$ 进行模型求解。求解之前，我们先给出以下引理。

引理1对于问题

$\underset{X}{\min }\frac{1}{2}{\Vert X-Z\Vert }_F^2+\lambda {\Vert X\Vert }_{2,p}^p$ (5)

的解为 $X^{\ast }=\text{Prox}\left(Z\right)$， $\text{Prox}\left(Z\right)=ZW$，其中W是对角矩阵，它的对角元素 $W_{ii}=\frac{{\varpi }_i}{{\Vert Z_i\Vert }_2}$， ${\varpi }_i=\arg {\min }_x\frac{1}{2}{\left(x-{\Vert Z_i\Vert }_2\right)}^2+{\left|x\right|}^p$。

引理2 $Q=\left[q_1;q_2;\cdots ;q_m\right]$ 为给定矩阵， $\lambda$ 是正标量，下列问题

$\underset{W}{\min }\frac{1}{2}{\Vert W-Q\Vert }_F^2+\lambda {\Vert W\Vert }_{2,1}$ (6)

的解为W，W的第i行为 $w_i=\{\begin{array}{l}\left(1-\frac{\lambda }{\Vert q_i\Vert }\right)q_i,\Vert q_i\Vert >\lambda \\ 0其它\end{array}$。

在第 $\tau +1$ 次迭代时，更新 ${\mathcal{X}}_{\tau +1}$ ：

${\mathcal{X}}_{\tau +1}=\arg \underset{\mathcal{X}}{\min }\frac{1}{2}{\Vert {\mathcal{P}}_{\Omega }\left(\mathcal{X}-\mathcal{T}\right)\Vert }_F^2+\frac{\mu }{2}{\Vert \mathcal{X}-{\mathcal{U}}_{\tau +1}\ast {\mathcal{V}}_{\tau +1}^{\text{T}}-{\mu }_{\tau }^{-1}{\mathcal{Y}}_{\tau }\Vert }_F^2$ (7)

然后，我们可以直接得到 ${\mathcal{X}}_{\tau +1}$ 的最优解

${\mathcal{X}}_{\tau +1}=\arg \underset{\mathcal{X}}{\min }{\mathcal{P}}_{{\Omega }^c}\left({\mathcal{U}}_{\tau +1}\ast {\mathcal{V}}_{\tau +1}^{\text{T}}-{\mu }_{\tau }^{-1}{\mathcal{Y}}_{\tau }\right)+{\mathcal{P}}_{\Omega }\left(\frac{\mathcal{T}+{\mu }_{\tau }{\mathcal{U}}_{\tau +1}\ast {\mathcal{V}}_{\tau +1}^{\text{T}}-{\mu }_{\tau }^{-1}{\mathcal{Y}}_{\tau +1}}{1+{\mu }_{\tau }}\right)$ (8)

其中 ${\mathcal{P}}_{{\Omega }^c}$ 是 ${\mathcal{P}}_{\Omega }$ 的互补算子。

在第 $\tau +1$ 次迭代时，更新 ${\mathcal{U}}_{\tau +1}$，我们将最小化与 $\mathcal{L}$ 的有关的 $\mathcal{U}$，同时保持所有其他变量不变。最小化问题变成

${\mathcal{U}}_{\tau +1}=\arg \underset{\mathcal{U}}{\min }\alpha {\Vert \mathcal{U}\Vert }_{2,q}^q+\langle {\mathcal{Y}}_{\tau },{\mathcal{X}}_{\tau }-\mathcal{U}\ast {\mathcal{V}}_{\tau }^{\text{T}}\rangle +\frac{\mu }{2}{\Vert {\mathcal{X}}_{\tau }-{\mathcal{U}}_{\tau }\ast {\mathcal{V}}_{\tau }^{\text{T}}\Vert }_F^2$ (9)

通过应用离散傅里叶变换并利用定理1的性质，(9)的解可以等价于在变换域中求解以下问题

${\bar{U}}_{\tau +1}^{\left(i\right)}=\arg \underset{{\bar{U}}^{\left(i\right)}}{\min }\alpha {\Vert {\bar{U}}^{\left(i\right)}\Vert }_{2,q}^q+\frac{L_{\tau +1}^U}{2}{\Vert {\bar{U}}^{\left(i\right)}-{\bar{U}}_{\tau }^{\left(i\right)}+{\left(L_{\tau +1}^U\right)}^{-1}\ast {\bar{Q}}_{\tau +1}^{\left(i\right)}\Vert }_F^2$ (10)

其中 ${\bar{Q}}_{\tau +1}^{\left(i\right)}={\mu }_{\tau }\left({\bar{X}}_{\tau }^{\left(i\right)}-{\bar{U}}_{\tau }^{\left(i\right)}{\left({\bar{V}}_{\tau }^{\left(i\right)}\right)}^{\text{T}}+{\bar{Y}}_{\tau }^{\left(i\right)}/{\mu }_{\tau }\right)\left(-{\bar{V}}_{\tau }^{\left(i\right)}\right)$， $L_{\tau +1}^U\ge \text{max}\left\{{\mu }_{\tau }{\Vert -{\bar{V}}_{\tau }^{\left(i\right)}\Vert }_2^2,i=1,\cdots ,n_3\right\}$。

根据引理1可求解。

在第 $\tau +1$ 次迭代时，更新 ${\mathcal{V}}_{\tau +1}$，们将最小化与 $\mathcal{L}$ 的有关的 $\mathcal{V}$，同时保持所有其他变量不变。最小化问题变成

${\bar{V}}_{\tau +1}^{\left(i\right)}=\arg \underset{{\bar{V}}^{\left(i\right)}}{\min }\beta {\Vert {\bar{V}}^{\left(i\right)}\Vert }_{2,q}^q+\frac{L_{\tau +1}^V}{2}{\Vert {\bar{V}}^{\left(i\right)}-{\bar{V}}_{\tau }^{\left(i\right)}+{\left(L_{\tau +1}^V\right)}^{-1}\ast {\bar{K}}_{\tau +1}^{\left(i\right)}\Vert }_F^2$ (11)

其中 ${\bar{K}}_{\tau +1}^{\left(i\right)}={\mu }_{\tau }\left(-{\left({\bar{U}}_{\tau }^{\left(i\right)}\right)}^{\text{T}}\right)\left({\bar{X}}_{\tau }^{\left(i\right)}-{\bar{U}}_{\tau +1}^{\left(i\right)}{\left({\bar{V}}_{\tau }^{\left(i\right)}\right)}^{\text{T}}+{\bar{Y}}_{\tau }^{\left(i\right)}/{\mu }_{\tau }\right)$， $L_{\tau +1}^V\ge \max \left\{\left({\mu }_{\tau }{\Vert {\bar{U}}_{\tau }^{\left(i\right)}\Vert }_2^2\right),i=1,\cdots ,n_3\right\}$。

根据引理2可求解。

在第 $\tau +1$ 次迭代时，更新 ${\mathcal{Y}}_{\tau +1}$ 和 ${\mu }_{\tau +1}$

${\mathcal{Y}}_{\tau +1}={\mathcal{Y}}_{\tau }+{\mu }_{\tau }\left({\mathcal{X}}_{\tau +1}-{\mathcal{U}}_{\tau +1}\ast {\mathcal{V}}_{\tau +1}^{\text{T}}\right)$ (12)

${\mu }_{\tau +1}=\min \left(\rho {\mu }_{\tau },{\mu }_{\max }\right)$ (13)

其中 $\rho >1$ 为常数参数， ${\mu }_{\max }$ 为默认最大值，可防止 $\mu$ 变得过大。

4. 实验

在本节中选取了大小为300 × 300 × 3的图片进行了实验，当自然图像转换为矩阵时，可以被视为低秩结构，张量数据也是如此。该图显示采样率为0.4，本文的方法与其他方法对比进行图像恢复的结果，以验证本文所提出算法的有效性和效率。将本文模型取p = 1/2和p = 2/3时的算法与张量的TNN和TCTF进行比较，并选择所有方法的参数，以确保它们尽可能好地执行。将结果和原始图片进行了比较。通过各种方法恢复的视觉结果如图1所示。并选择时间(TIME)、峰值信噪比(PSNR)和结构化相似性指数(SSIM)作为评估指标的结果如表1所示。PSNR和SSIM的数值越大，实验效果越好。

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

Figure 1. The results of image in painting, where (a) is original image; (b) is observation; (c) is DFTN1/2; (d) is DFTN2/3; (e) is TCTF; (f) is TNN

图1. 不同算法的图像修复的结果，其中(a) 是原始图像；(b) 是观察图像；(c) 是DFTN1/2；(d) 是DFTN2/3；(e) 是TCTF；(f) 是TNN

Table 1. Comparison of PSNR, SSIM and computation time for image inpainting

表1. 图像修复的PSNR、SSIM和计算时间的比较

5. 结论

本文中提出了双因子张量范数正则化低秩张量填充模型，并给出了求解低秩张量补全的有效算法。在这个优化过程中，避免了大规模张量的奇异值分解。此外，我们选取p = 1/2和p = 2/3的算法模型，通过真实数据的实验，从精度和时间消耗两个方面验证了该算法的优越性。

基金项目

该文得到了辽宁省高等学校创新人才支持计划的资助。

NOTES

^*通讯作者。