改进的鲁棒低秩正则化张量填充

Improved Robust Low-Rank Regularization Tensor Completion

摘要: 考虑到传统张量核范数作为秩函数的凸松弛在实际优化效果上的不足，本文借助非凸松弛的思想，提出了由加权张量核范数和加权张量Frobenius范数组合而成的新的非凸的张量填充模型，并运用交替方向乘子法求解所提出的低秩张量恢复模型。在张量填充方面，该模型在PSNR指标和视觉感知方面均优于传统方法，也取得了比传统算法更好的性能。

Abstract: Considering the deficiency of the convex relaxation of the traditional tensor nuclear norm as a rank function in the actual optimization effect, this paper proposes a new non convex tensor completion model composed of weighted tensor nuclear norm and weighted tensor Frobenius norm by virtue of the idea of non convex relaxation, and uses the alternating direction multiplier method to solve the proposed low rank tensor recovery model. In terms of tensor filling, the model is superior to the traditional methods in terms of PSNR index and visual perception, and has achieved better perfor-mance than the traditional algorithm.

1. 引言

在计算机视觉和信号处理等领域，人们所需要收集、储存和处理的数据不仅规模庞大，而且具有维度极其高，结构极其复杂的显著特点。作为多维数据的自然表示，张量是向量和矩阵的高阶形式的推广。近年来，关于张量的研究已经扩展到机器学习 [1]、模式识别 [2] 和图像处理 [3] 等许多领域。然而在实际生活中，观察到的数据可能会部分丢失或者存在噪声，因此在噪声和缺失值的影响下，如何准确地对真实数据进行有效鲁棒恢复是当前研究热点。

张量填充问题旨在从一个不完整的观测数据中精确地恢复低秩张量，其数学模型如下：

$\underset{\mathcal{X}}{\text{min}}rank\left(\mathcal{X}\right)\text{s}\text{.t}.P_{\Omega }\left(\mathcal{X}\right)=P_{\Omega }\left(\mathcal{M}\right)$ (1)

其中， $\mathcal{X}\in {ℝ}^{n_1\times n_2\times n_3}$ 是恢复的低秩张量， $\mathcal{T}\in {ℝ}^{n_1\times n_2\times n_3}$ 是观测张量，P为投影算子， $\Omega$ 为观测元素的索引集， $rank\left(\mathcal{X}\right)$ 为张量 $\mathcal{X}$ 的秩函数。由于张量秩函数是非凸非光滑的，上述模型是一个NP难问题，并且有关张量秩的定义的研究至今仍然是一个开放的问题。因此，关于低秩张量填充模型的求解方法一直是低秩张量填充问题的重要研究内容。

最流行的两种张量秩定义是基于Tucker分解的Tucker秩 [4]，以及基于CANDECOMP/PARAFAC (CP)分解的CP-秩 [5]。但是指出CP秩的计算一般为NP难问题，并且其凸松弛是难以处理的。同时Liu等人 [6] 指出Tucker分解中的这种矩阵化技术不能利用完全所有的结构信息。为了突破张量秩函数定义的局限性，Kilmer [7] 提出了一种新的张量分解范式，即张量奇异值分解(Tensor Singular Value Decomposition, T-SVD)。利用T-SVD，在张量积(T-积)及其代数框架的基础上，定义了张量管秩的概念。T-SVD可以将矩阵分解扩展到张量，同时避免了张量矩阵化过程中固有的信息丢失。管秩可以很好地表征张量的内在结构。因此，近年来涌现出越来越多关于低管秩张量填充问题的合理研究。

解决低管秩张量填充问题，最常用数学模型是利用张量核范数来近似张量管秩。Lu等人 [8] 首先定义了张量平均秩，并推导出如果一个张量具有低的管秩，则其平均秩总是低的，然后提出了一个新的张量核范数，其张量填充模型如下：

$\underset{\mathcal{X}}{\text{min}}{\Vert \mathcal{X}\Vert }_{\ast }\text{s}\text{.t}\text{.}{P}_{\Omega }\left(\mathcal{X}\right)=P_{\Omega }\left(\mathcal{M}\right)$ (2)

其中， ${\Vert \mathcal{X}\Vert }_{\ast }$ 为张量 $\mathcal{X}$ 的核范数。该范数被证明是张量平均秩在张量谱范数的单位球内的凸包络，在许多任务中表现得比其他类型的张量核范数好得多。

尽管张量核范数已经成为解决低管秩张量填充问题的有效方法，但是由于张量核范数是对所有奇异值同时最小化，并且所得到的全局最优解可能会明显偏离基本事实，这使得该凸松弛方法在解决问题的时候具有局限性。目前已有学者尝试通过非凸松弛方法对张量填充进行研究 [9] [10] [11] [12]，非凸替代能够克服不同奇异值的不平衡惩罚，本质上，它们会保持较大的奇异值的同时缩小较小的奇异值。并取得了成功。大量的实验结果证明，该方法显著提高了低管秩张量填充问题的精准度和鲁棒性。

2. 预备知识

定理 1 [7] 张量奇异值分解：设张量 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$，则 $\mathcal{A}$ 的奇异值分解为 $\mathcal{A}=\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_1\times n_2\times n_3}$ 是对角张量。

定义 1 [7] 张量管秩：设张量 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$， $\mathcal{A}$ 的奇异值分解为 $\mathcal{A}=\mathcal{U}\ast \mathcal{S}\ast {\mathcal{V}}^{\text{T}}$，张量管秩等价于张量的非零奇异值的个数，定义为 $\mathcal{S}$ 的非零奇异管的个数，记作 $ran{k}_t\left(\mathcal{A}\right)$，

$ran{k}_t\left(\mathcal{A}\right)=\text{\#}\left\{i\text{,}\mathcal{S}\left(i,i,j\right)\ne \text{0}\right\}=\text{\#}\left\{i\text{,}\mathcal{S}\left(i,i,1\right)\ne \text{0}\right\}$

其中， $\mathcal{S}\left(i,i,1\right)=\frac{1}{n_3}{\displaystyle {\sum }_{j=1}^{n_3}\bar{\mathcal{S}}\left(i,i,1\right)}$，若记 $\sigma \left(\mathcal{A}\right)\in {ℝ}^{n\times n_3}$ 为张量奇异值矩阵， $n=\min \left\{n_1,n_2\right\}$， ${\sigma }_{ij}\left(\mathcal{A}\right)=\bar{\mathcal{S}}\left(i,i,j\right)$，那么张量核范数和张量Frobenius范数可以定义如下。

定义 2 [8] 张量核范数：设张量 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$， $\mathcal{A}$ 的奇异值分解为 $\mathcal{A}=\mathcal{U}\ast \mathcal{S}\ast {\mathcal{V}}^{\text{T}}$，张量核范数记为：

${\Vert \mathcal{A}\Vert }_{*}=\frac{1}{n_3}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n_3}{\sum }}{\sigma }_{ij}(\; A\; )}}$

定义 3 张量Frobenius范数：设张量 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$， $\mathcal{A}$ 的奇异值分解为 $\mathcal{A}=\mathcal{U}\ast \mathcal{S}\ast {\mathcal{V}}^{\text{T}}$，张量Frobenius范数记为：

${\Vert \mathcal{A}\Vert }_F=\frac{1}{\sqrt{n_3}}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n_3}{\sum }}\sqrt{{\sigma }_{ij}^2(\; A\; )}}}$

3. 加权核范数和Frobenius范数的正则化低秩张量填充

根据定义2和定义3中张量核范数和张量Frobenius范数的定义。本文提出了一种新的非凸正则化，该正则化定义为加权张量核范数与加权张量Frobenius范数(WTNFN)的平方之和：

${\Vert \mathcal{X}\Vert }_{W,*}+\gamma {\Vert \mathcal{X}\Vert }_{W,F}^2=\frac{1}{n_3}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n_3}{\sum }}({\sigma }_{ij}\left(\mathcal{X}\right)+\gamma {\sigma }_{ij}^2(\; X\; )})}$

其中， $W=\left(w_{ij}\right){}_{n\times n_3}$ 为权重矩阵， $n=\min \left\{n_1,n_2\right\}$， $\gamma$ 为正参数。

3.1. 模型确立

低秩张量填充问题旨在从一个不完全观测值中精确地恢复一个低秩张量，在T-SVD代数框架 [8] 下，考虑到传统张量核范数作为秩函数的凸松弛在实际优化效果上的不足，借助非凸松弛的思想，本节引入一种新的正则化方法来提高张量填充的鲁棒性。即加权核范数和Frobenius范数张量填充，问题模型如下：

$\underset{\mathcal{X}}{\text{min}}{\Vert \mathcal{X}\Vert }_{W,\ast }+\gamma {\Vert \mathcal{X}\Vert }_{W,F}^{\text{2}}\text{s}\text{.t}.P_{\Omega }\left(\mathcal{X}\right)=P_{\Omega }\left(\mathcal{M}\right)$ (3)

其中， $\mathcal{X}\in {ℝ}^{n_1\times n_2\times n_3}$ 是恢复的低秩张量， $\mathcal{M}\in {ℝ}^{n_1\times n_2\times n_3}$ 是观测张量，P为投影算子， $\Omega$ 与 $\mathcal{M}$ 大小相同的观测元素索引集。 $\Omega$ 中的零表示观察到的张量中缺失的元素，而 $P_{\Omega }:{ℝ}^{n_1\times n_2\times n_3}\to {ℝ}^{n_1\times n_2\times n_3}$ 是一个线性算子，它保持元素不变，并将这些元素设置为零以外的值。 $P_{\Omega }\left(\mathcal{M}\right)=\mathcal{M}\odot \Omega$ 是索引集 $\Omega$ 和张量 $\mathcal{M}\in {ℝ}^{n_1\times n_2\times n_3}$ 之间的元素哈达玛乘积。上述约束意味着估计的张量 $\mathcal{X}$ 与观测的张量 $\mathcal{M}$ 一致。通过引入一个变量 $\mathcal{E}$，将(3)重新表述为：

$\underset{\mathcal{X}}{\text{min}}{\Vert \mathcal{X}\Vert }_{W,\ast }+\gamma {\Vert \mathcal{X}\Vert }_{W,F}^{\text{2}}\text{s}\text{.t}\text{.}\mathcal{E}=\mathcal{X},P_{\Omega }\left(\mathcal{X}\right)=P_{\Omega }\left(\mathcal{M}\right)$ (4)

因此，优化问题(3)可以等价的转化为优化问题(4)，下面将对模型进行求解。

3.2. 模型求解

采用交替方向乘子法(Alternating Direction Multiplier Method, ADMM)解决上述具有约束的优化问题，首先将(4)式转化为如下无约束的增广拉格朗日函数：

$\mathcal{L}\left(\mathcal{X},\mathcal{E},\mathcal{Y},\mu \right)={\Vert \mathcal{X}\Vert }_{W,*}+\gamma {\Vert \mathcal{X}\Vert }_{W,F}^2+\langle \mathcal{Y},\mathcal{X}-\mathcal{E}\rangle +\frac{\mu }{2}{\Vert \mathcal{X}-\mathcal{E}\Vert }_F^2$ (5)

其中， $\mathcal{Y}$ 是拉格朗日乘子， $\mu$ 是大于零的惩罚参数。那么(5)式第k + 1迭代的结果可以看做是解决如下几个子问题。

· 假设 ${\mathcal{X}}_k,{\mu }_k,{\mathcal{Y}}_k$ 是第k次迭代的结果，保持其他变量固定，更新 ${\mathcal{E}}_{k+1}$ ：

$\begin{array}{c}{\mathcal{E}}_{k+1}=\underset{\mathcal{E}}{\arg \min }\langle {\mathcal{Y}}_k,{\mathcal{X}}_k-\mathcal{E}\rangle +\frac{{\mu }_k}{2}{\Vert {\mathcal{X}}_k-\mathcal{E}\Vert }_F^2\\ =\underset{\mathcal{E}}{\arg \min }\frac{{\mu }_k}{2}{\Vert {\mathcal{X}}_k-\mathcal{E}+{\mu }_k^{-1}{\mathcal{Y}}_k\Vert }_F^2\end{array}$ (6)

由此可见， ${\mathcal{E}}_{k+1}$ 迭代可化为二次函数，那么通过简单推导可以得到

${\mathcal{E}}_{k+1}={\mathcal{X}}_k+{\mu }_k^{-1}{\mathcal{Y}}_k$ (7)

· 假设 ${\mathcal{X}}_k,{\mathcal{E}}_k,{\mu }_k$ 是第k次迭代的结果，保持其他变量固定，更新 ${\mathcal{Y}}_{k+1}$ ：

${\mathcal{Y}}_{k+1}=\mathcal{Y}+{\mu }_k\left({\mathcal{X}}_k-{\mathcal{E}}_k\right)$ (8)

· 假设 ${\mathcal{X}}_k,{\mathcal{E}}_k,{\mathcal{Y}}_k$ 是第k次迭代的结果，保持其他变量固定，更新 ${\mu }_{k+1}$ ：

${\mu }_{k+1}=\rho \ast {\mu }_k$ (9)

其中， $\rho$ 是大于1的参数。

· 假设 ${\mathcal{Y}}_k,{\mathcal{E}}_k,{\mu }_k$ 是第k次迭代的结果，保持其他变量固定，更新 ${\mathcal{X}}_{k+1}$ ：

$\begin{array}{c}{\mathcal{X}}_{k+1}=\underset{\mathcal{X}}{\arg \min }{\Vert \mathcal{X}\Vert }_{W,*}+\gamma {\Vert \mathcal{X}\Vert }_{W,F}^2+\langle {\mathcal{Y}}_k,\mathcal{X}-{\mathcal{E}}_k\rangle +\frac{{\mu }_k}{2}{\Vert \mathcal{X}-{\mathcal{E}}_k\Vert }_F^2\\ =\underset{\mathcal{X}}{\arg \min }{\Vert \mathcal{X}\Vert }_{W,*}+\gamma {\Vert \mathcal{X}\Vert }_{W,F}^2+\frac{{\mu }_k}{2}{\Vert \mathcal{X}-{\mathcal{E}}_k+{\mu }_k^{-1}{\mathcal{Y}}_k\Vert }_F^2\end{array}$ (10)

为了优化(10)式，引入定理2

定理2 设张量 $\mathcal{Y}\in {ℝ}^{n_1\times n_2\times n_3}$， $\mathcal{Y}$ 的奇异值分解为 $\mathcal{Y}=\mathcal{U}\ast \mathcal{S}\ast {\mathcal{V}}^{\text{T}}$，对于任何的 $\gamma >0$ 下述优化问题

$\underset{\mathcal{X}}{\min }\frac{1}{2}{\Vert \mathcal{X}-\mathcal{Y}\Vert }_F^2+{\Vert \mathcal{X}\Vert }_{W,*}+\gamma {\Vert \mathcal{X}\Vert }_{W,F}^2$ (11)

有全局最优解 ${\mathcal{D}}_{W,\gamma }\left(\mathcal{Y}\right)$，

${\mathcal{D}}_{W,\gamma }\left(\mathcal{Y}\right)=\mathcal{U}\ast {\mathcal{S}}_{W,\gamma }\ast {\mathcal{V}}^{\text{T}}$ (12)

其中， ${\mathcal{S}}_{W,\gamma }=ifft\left({\left({\left(1+2\gamma \mathcal{W}\right)}^{-1}\left(\bar{S}-\mathcal{W}\right)\right)}_{+},\left[\right],3\right)$， $\mathcal{W}\in R^{n_1\times n_2\times n_3}$ 是对角张量。

由定理2可得 ${\mathcal{X}}_{k+1}$ 的最后更新结果，假设 ${\mathcal{Y}}_k-{\mathcal{E}}_k$ 的奇异值分解为 ${\mathcal{Y}}_k-{\mathcal{E}}_k=\mathcal{U}\ast \Sigma \ast {\mathcal{V}}^{\text{T}}$

${\mathcal{X}}_{k+1}={\mathcal{D}}_{W,\gamma }\left({\mathcal{Y}}_k-{\mathcal{E}}_k\right)=\mathcal{U}\ast {\Sigma }_{W,\gamma }\ast {\mathcal{V}}^{\text{T}}$ (13)

其中， ${\mathcal{S}}_{W,\gamma }=ifft\left({\left({\left(1+2\gamma \mathcal{W}\right)}^{-1}\left(\bar{\Sigma }-\mathcal{W}\right)\right)}_{+},\left[\right],3\right)$。

综上，将子问题进行结合，最终得到问题(3)的最优解。

4. 实验

本节中将上节提出的加权张量核范数和Frobenius范数应用到真实彩色去噪实验，并且与张量核范数(TNN)真实彩色图像去噪实验、张量截断核范数(TNNR)真实彩色图像去噪实验和张量因子分解(TCTF)真实彩色图像去噪实验来作比较。实验的彩色图片大小为300 × 300 × 3，所有实验均设置在随机噪声50%下进行彩色图片恢复，通过比较四种方法恢复真实彩色图像的视觉效果和峰值性噪比(PSNR)，来说明本文所提出的正则化方法的优越性。图1将四种恢复模型去噪后得到的真实彩色图像与无噪声原始彩色图像相比较，显然本文恢复模型在视觉效果上优于其他三种方法。表1列出四种模型恢复图像所得PSNR值(PSNR值越高证明图像恢复效果越好)，由此可得本文恢复模型在相同情况下与其他三种方法相比能够得到相对较高的PSNR值。

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

Figure 1. Performance comparison for image recovery on some sample images. (a) Original image; (b) observed image; (c) recovered images by ours; (d) recovered images byTNN; (e) recovered images by TNNR; (f) recovered images by TCTF

图1. 在部分样本图像上进行图像恢复的性能比较。(a) 原始图像；(b) 观察图像；(c) 我们的方法恢复图像；(d) TNN恢复图像；(e) TNNR恢复图像；(f) TCTF恢复图像

Table 1. Comparison of PSNR values for real color image restoration

表1. 真实彩色图像恢复的PSNR值对比

5. 结论

本文提出了一种新的方法称为加权核和Frobenius范数正则化的低秩张量填充，为了优化基于加权张量核范数和Frobenius范数范数的最小化问题，利用ADMM算法经过详细推导得到加权张量核和Frobenius范数奇异值阈值算子，将提出的加权张量核范数和Frobenius范数模型应用于真实数据去噪实验，该模型在PSNR指标和视觉感知方面均取得了比较好的性能。

基金项目

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