¹辽宁师范大学，辽宁 大连

²温州大学，浙江 温州

收稿日期：2022年9月10日；录用日期：2022年10月2日；发布日期：2022年10月10日

摘要

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

关键词

低秩张量恢复，张量Schatten-p范数，分解

Double Factor Tensor Norm Regularized Low Rank Tensor Completion

Hongyan Li^1*, Wei Jiang^1,2

¹Liaoning Normal University, Dalian Liaoning

²Wenzhou University, Wenzhou Zhejiang

Received: Sep. 10^th, 2022; accepted: Oct. 2^nd, 2022; published: Oct. 10^th, 2022

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 ${\mathcal{l}}_{2,q}$ -norm and ${\mathcal{l}}_{2,1}$ -norm, the problem of solving the tensor Schatten-p norm requiring tensor singular value decomposition 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 effectiveness of the algorithm in terms of accuracy and time complexity.

Keywords:Recovery Problem of Low Rank Tensors, T-Schatten-p Norm, Decompose

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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的数值越大，实验效果越好。

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

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

5. 结论

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

基金项目

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

文章引用

李鸿燕,姜 伟. 双因子张量范数正则化低秩张量填充
Double Factor Tensor Norm Regularized Low Rank Tensor Completion[J]. 应用数学进展, 2022, 11(10): 6908-6914. https://doi.org/10.12677/AAM.2022.1110732

参考文献