基于混合截断范数的张量鲁棒主成分分析

Tensor Robust Principal Component Analysis Based on Hybrid Truncation Norm

摘要: 本文将截断核范数正则化的思想推广到张量鲁棒主成分分析。为提高模型的稳定性，新定义了张量截断Frobenius范数，并给出同时考虑张量截断核范数和截断Frobenius范数的混合截断模型。这种方法只会最小化min(m,n)-r个奇异值。此外，本文还给出一种确定收缩算子的有效方法，并为此方法开发了一种基于交替方向的有效迭代算法来解决这个优化问题。实验结果表明，该方法可以有效并准确地实现图像去噪。

Abstract: In this paper, the idea of truncated nuclear norm regularization is extended to tensor robust prin-cipal component analysis. In order to improve the stability of the model, the tensor truncated Fro-benius norm is defined, and a mixed truncated model considering both tensor truncated nuclear norm and truncated Frobenius norm is given. This method minimizes min(m,n)-r singular val-ues. In addition, this paper also gives an effective method to determine the contraction operator, and develops an effective iterative algorithm based on alternate directions to solve this optimiza-tion problem. The experimental results show that this method can effectively and accurately realize image denoising.

1. 引言

张量是矩阵的高阶推广，是一种重要的数据形式，可以表达更复杂的高阶数据的内部结构。事实上，张量也是高维真实世界数据的自然形式。例如，在图像处理领域，彩色图像是三阶张量，多光谱图像是三阶张量。因此，张量分析在机器学习 [1] [2]、计算机视觉 [2]、数据挖掘 [3] 等领域具有重要的现实意义和应用价值。而经典的主成分分析(PCA)是用于数据分析和降维的最广泛的方法，对于受小噪声轻微损坏的数据，它具有计算效率高、功能强大的特点。然而，主成分分析的一个主要问题是，它很容易受严重损坏或离奇的观测值影响，而这些观测值在现实世界的数据中无处不在。到目前为止，已经提出了许多主成分分析模型，但几乎都具有很高的计算成本。

最近提出的RPCA是第一个具有强大性能保证的多项式时间算法。假设有一个数据矩阵 $X\in {ℝ}^{m\times n}$ 可以被分解为： $X=L_0+E_0$，其中 $L_0$ 是低秩分量， $E_0$ 是稀疏分量。文献 [1] 表明，如果 $L_0$ 的奇异向量满足某些非相干条件，例如， $L_0$ 是低秩的，并且 $E_0$ 足够稀疏，则可以通过求解凸问题

$\begin{array}{l}\underset{L,E}{\min }{\Vert L\Vert }_{\ast }+\lambda {\Vert E\Vert }_1\\ \text{s}\text{.t}\text{.}X=L+E\end{array}$，

以高概率精确的恢复 $L_0$ 和 $E_0$。其中 ${\Vert L\Vert }_{\ast }$ 表示 $L$ 的核范数， ${\Vert E\Vert }_1$ 表示 $E$ 的 ${\mathcal{l}}_1$ 范数，且 $\lambda$ 通常设置为 $1/\sqrt{\max \left(n_1,n_2\right)}$。在算法上，可以通过高效的算法求解，成本不会比PCA高太多。该方法已成功应用于背景建模、子空间聚类、视频压缩感知等领域。

将RPCA推广到张量并不容易，本文研究了张量鲁棒主成分分析(TRPCA) [4]，旨在准确恢复被稀疏噪声损坏的低秩张量，提出一种新的张量鲁棒主成分分析方法，试图建立一个更稳定、更理想的模型。本文提出了两个新的正则化项，张量截断核范数(T-TNN)和张量截断Frobenius范数(T-TFN)。基于这两个新定义，提出了张量混合截断范数模型(T-HTN)，该模型利用(T-TNN)和(T-TFN)的组合来实现张量鲁棒主成分分析，该模型不仅提高了稳定性，而且有效地提高了恢复精度。

2. 预备知识

在这一部分，我们主要介绍新定义的张量截断核范数和张量截断Frobenius范数，在此基础上提出一种混合截断范数模型来提高张量鲁棒主成分分析算法的有效性和模型的稳定性并给出该模型的迭代求解方法。

定义1 (张量奇异值分解)：张量 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ 可被分解为： $\mathcal{A}=\mathcal{U}\ast {}_L\mathcal{S}\ast {}_L\mathcal{V}{}^{\text{T}}$，其中 $\mathcal{U}\in {ℝ}^{n_1\times n_1\times n_3}$， $\mathcal{V}\in {ℝ}^{n_2\times n_2\times n_3}$ 是正交张量， $\mathcal{S}\in {ℝ}^{n_2\times n_2\times n_3}$ 是F对角张量。

定义2 (张量核范数)：对于张量 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$，它的奇异值分解为： $\mathcal{A}=\mathcal{U}\ast {}_L\mathcal{S}\ast {}_L\mathcal{V}{}^{\text{T}}$，则张量 $\mathcal{A}$ 的核范数定义为 $\mathcal{S}$ 的所有正面切片的奇异值之和，即：

${\Vert \mathcal{A}\Vert }_{\ast }={\displaystyle \underset{i=1}{\overset{r}{\sum }}\mathcal{S}\left(i,i,1\right)}=\frac{1}{n_3}{\Vert \bar{A}\Vert }_{\ast }$

定义3 (张量奇异值阈值算子(T-SVT))：对于张量 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$，它的奇异值分解为： $\mathcal{A}=\mathcal{U}\ast \mathcal{S}\ast {\mathcal{V}}^{\text{T}}$，对任意的 $\tau >0$，张量 $\mathcal{A}$ 的奇异值阈值算子记作： ${\mathcal{D}}_{\tau }\left(\mathcal{A}\right)$，应用在 $\bar{\mathcal{S}}$ 的每个正面切片上，即：

${\mathcal{D}}_{\tau }\left(\mathcal{A}\right)=\mathcal{U}\ast {}_L\mathcal{S}{}_{\tau }\ast {}_L\mathcal{V}{}^{\text{T}}$

定义4 (张量截断核范数(T-TNN))：给定张量 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$，截断核范数 ${\Vert \mathcal{A}\Vert }_{r,\ast }$ 定义为 $\bar{\mathcal{A}}$ 的每一个正面切片的后min $\left(m,n\right)-r$ 个奇异值的和，即：

${\Vert \mathcal{A}\Vert }_{r,\ast }={\Vert \mathcal{A}\Vert }_{\ast }-\frac{1}{n_3}{\displaystyle \underset{i=1}{\overset{n_3}{\sum }}{\displaystyle \underset{j=1}{\overset{r}{\sum }}{\sigma }_j({\bar{A}}^{(\; i\; )})}}$

其中 ${\sigma }_j\left({\bar{A}}^{\left(i\right)}\right)$ 为 ${\bar{A}}^{\left(i\right)}\in {ℝ}^{n_1\times n_2}$ 的第j个奇异值。

定义5 (张量截断Frobenius范数(T-TFN))：给定张量 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$，其截断Frobenius范数定义为 $\bar{\mathcal{A}}$ 的每一个正面切片的后min $\left(m,n\right)-r$ 个奇异值的平方和的平方根，即：

${\Vert \mathcal{A}\Vert }_{r,F}=\frac{1}{\sqrt{n_3}}{\displaystyle \underset{i=1}{\overset{n_3}{\sum }}\sqrt{{\displaystyle \underset{j=1}{\overset{\min \left(n_1,n_2\right)}{\sum }}{\left({\sigma }_j\left({\bar{A}}^{\left(1\right)}\right)\right)}^2}-{\displaystyle \underset{j=1}{\overset{r}{\sum }}{\left({\sigma }_j\left({\bar{A}}^{\left(1\right)}\right)\right)}^2}}}$

因此， ${\Vert \mathcal{A}\Vert }_{r,F}^2$ 为

${\Vert \mathcal{A}\Vert }_{r,F}^2={\Vert \mathcal{A}\Vert }_F^2-\frac{1}{n_3}{\displaystyle \underset{i=1}{\overset{n_3}{\sum }}{\displaystyle \underset{j=1}{\overset{r}{\sum }}{\left({\sigma }_j\left({\bar{A}}^{\left(1\right)}\right)\right)}^2}}$

定义6 (张量管秩)张量 $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ 的奇异值分解为 $\mathcal{A}=\mathcal{U}\ast {}_L\mathcal{S}\ast {}_L\mathcal{V}{}^{\text{T}}$，则张量 $\mathcal{A}$ 的管秩 $ran{k}_t\left(\mathcal{A}\right)$ 定义为 $\mathcal{S}$ 的非零奇异管的个数，即：

$ran{k}_t\left(\mathcal{A}\right)=\#\left\{i,\mathcal{S}\left(i,i,:\right)\ne 0\right\}=\#\left\{i,\mathcal{S}\left(i,i,1\right)\ne 0\right\}=\max \left(r_1,\cdots ,r_{n_3}\right)$.

3. 混合截断范数张量鲁棒主成分分析

3.1. 模型建立

由定义4，和定义5易知，T-TNN和T-TFN均只考虑了每一个正面切片的后min $\left(m,n\right)-r$ 个奇异值，故可将二者结合，建立更加有效的混合截断张量鲁棒主成分分模型(T-HTN-RPCA)：

$\begin{array}{l}\underset{\mathcal{X}}{\min }:{\Vert \mathcal{L}\Vert }_{r,\ast }+\gamma {\Vert \mathcal{L}\Vert }_{r,F}^2+\lambda {\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}\text{.}\mathcal{X}=\mathcal{L}+\mathcal{E}\end{array}$ (1)

由 [5] 知， ${\Vert \mathcal{L}\Vert }_{r,\ast }={\Vert \mathcal{L}\Vert }_{\ast }-\underset{\begin{array}{l}{\mathcal{A}}^{\text{T}}\mathcal{A}=\mathcal{I}\\ {\mathcal{B}}^{\text{T}}\mathcal{B}=\mathcal{I}\end{array}}{\max }Tr\left(\mathcal{A}\ast \mathcal{L}\ast {\mathcal{B}}^{\text{T}}\right)$， ${\Vert \mathcal{L}\Vert }_{r,F}^2={\Vert \mathcal{L}\Vert }_F^2-\underset{{\mathcal{A}}^{\text{T}}\mathcal{A}=\mathcal{I}}{\max }{\Vert \mathcal{A}\ast \mathcal{L}\Vert }_F^2$。因此T-HTN—RPCA模型可表示为：

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }:{\Vert \mathcal{L}\Vert }_{\ast }-\underset{\begin{array}{l}{\mathcal{A}}^{\text{T}}\mathcal{A}=\mathcal{I}\\ {\mathcal{B}}^{\text{T}}\mathcal{B}=\mathcal{I}\end{array}}{\max }Tr\left(\mathcal{A}\ast \mathcal{L}\ast {\mathcal{B}}^{\text{T}}\right)+\gamma \left({\Vert \mathcal{L}\Vert }_F^2-\underset{{\mathcal{A}}^{\text{T}}\mathcal{A}=\mathcal{I}}{\max }{\Vert \mathcal{A}\ast \mathcal{L}\Vert }_F^2\right)+\lambda {\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}.\mathcal{X}=\mathcal{L}+\mathcal{E}\end{array}$ (2)

3.2. 模型求解

为了求解优化问题(2)，本节提出一种有效的迭代方法，可以分为以下两个步骤：

第一步，令 ${\mathcal{L}}_0=\mathcal{O}$ 作为 $\mathcal{L}$ 的初始值，在第l次迭代中，固定 ${\mathcal{L}}_l$，将 ${\mathcal{L}}_l$ 奇异值分解为 ${\mathcal{L}}_l=\mathcal{U}\ast \mathcal{Q}\ast {\mathcal{V}}^{\text{T}}$，其中 $\mathcal{U}\in {ℝ}^{n_1\times r\times n_3}$， $\mathcal{V}\in {ℝ}^{n_2\times r\times n_3}$， $\mathcal{Q}\in {ℝ}^{n_1\times n_2\times n_3}$，记 ${\mathcal{A}}_l=\mathcal{U}{\left(:,1:r,:\right)}^{\text{T}}\in {ℝ}^{r\times n_1\times n_3}$， ${\mathcal{B}}_l=\mathcal{V}{\left(:,1:r,:\right)}^{\text{T}}\in {ℝ}^{r\times n_2\times n_3}$。

第二步，固定 ${\mathcal{A}}_l$， ${\mathcal{B}}_l$，通过求解下述最小化问题来更新 ${\mathcal{L}}_{l+1}$， ${\mathcal{E}}_{l+1}$ ：

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }:{\Vert \mathcal{L}\Vert }_{\ast }-Tr\left({\mathcal{A}}_l\ast \mathcal{L}\ast {\mathcal{B}}_l^{\text{T}}\right)+\gamma \left({\Vert \mathcal{L}\Vert }_F^2-{\Vert {\mathcal{A}}_l\ast \mathcal{L}\Vert }_F^2\right)+\lambda {\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}\text{.}\mathcal{X}=\mathcal{L}+\mathcal{E}\end{array}$ (3)

简言之，本节实现了这两个步骤，且在它们之间交替进行，直至满足迭代误差限。现在的关键问题是如何求解模型(3)，这会在下一小节中讨论。

3.3. 优化方法

对于模型(3)，本节给出了一个有效的优化方法。增广的拉格朗日乘子法综合了拉格朗日乘子法和二次惩罚法各自的优点，不仅推广了拉格朗日乘子法的适用范围，同时又避免了二次惩罚带来的病态性。根据增广拉格朗日乘子法，常用的策略是利用交替迭代来近似最小增广拉格朗日函数，本文继续延用此策略进行求解。为使变量可分，首先引入辅助变量 $\mathcal{Z}$，此时(3)等价于

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }:{\Vert \mathcal{L}\Vert }_{\ast }-Tr\left({\mathcal{A}}_l\ast \mathcal{Z}\ast {\mathcal{B}}_l^{\text{T}}\right)+\gamma \left({\Vert \mathcal{L}\Vert }_F^2-{\Vert {\mathcal{A}}_l\ast \mathcal{L}\Vert }_F^2\right)+\lambda {\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}.\mathcal{L}=\mathcal{Z}\mathcal{X}=\mathcal{L}+\mathcal{E}\end{array}$ (4)

(4)式的增广拉格朗日函数为：

(5)

其中 $\mathcal{Y},\mathcal{W}$ 是拉格朗日乘子， $\alpha ,\beta >0$ 是惩罚参数。故可以采用交替迭代方法：通过固定一些变量来求解剩余的那个变量。具体优化过程如下：

步骤一：保持不变，通过更新 ${\mathcal{E}}_{k+1}$ ：

(6)

步骤二：保持不变，通过更新 ${\mathcal{L}}_{k+1}$ ：

(7)

步骤三：保持不变，通过更新 ${\mathcal{Z}}_{k+1}$ ：

(8)

显然，(8)式是一个二次函数，因此通过简单的求导可以得到：

$-{\mathcal{A}}_l^{\text{T}}\ast {\mathcal{B}}_l-{\mathcal{W}}_k-\alpha {\mathcal{L}}_{k+1}+\alpha \mathcal{Z}=0$.

于是有：

${\mathcal{Z}}_{k+1}={\mathcal{L}}_{k+1}+{\alpha }^{-1}\left({\mathcal{A}}_l^{\text{T}}\ast {\mathcal{B}}_l+{\mathcal{W}}_k\right)$. (9)

步骤四：更新拉格朗日乘子 ${\mathcal{Y}}_{k+1}$， ${\mathcal{W}}_{k+1}$ ：

$\begin{array}{l}{\mathcal{Y}}_{k+1}={\mathcal{Y}}_k+\beta \left({\mathcal{X}}_{k+1}-{\mathcal{L}}_{k+1}-{\mathcal{E}}_{k+1}\right)\\ {\mathcal{W}}_{k+1}={\mathcal{W}}_k+\alpha \left({\mathcal{L}}_{k+1}-{\mathcal{Z}}_{k+1}\right)\end{array}$ (10)

综上所述，完整程序如表1所示。

Table 1. Solve (3) by ADMM

表1. 基于ADMM对(3)式的求解

4. 实验

我们将进行数值实验以确认我们的主要结果。我们研究了T-HTN从各种稀疏噪声中恢复各种管状秩张量的能力，并将T-HTN应用于图像去噪。

数值实验

在本节，我们评估了本文提出的T-HTN在实际数据集上的效率，并将其与TRPCA进行了比较。具体来说，我们对彩色图像数据进行张量恢复实验。目的是从损坏的观察中恢复原始图像。对于基本张量 ${\mathcal{L}}^{\ast }$ 的估计，我们选择相对平方误差(RSE)和峰值信噪比(Peak Signal-to-Noise Ratio, PSNR)作为评估指标，分别定义为

$\text{RSE}\left(\hat{\mathcal{L}},{\mathcal{L}}^{*}\right):=\frac{{\Vert \hat{\mathcal{L}}-{\mathcal{L}}^{*}\Vert }_F}{{\Vert {\mathcal{L}}^{*}\Vert }_F}$

$\text{PSNR}=10{\log }_{10}\left(\frac{n_1{n}_2{n}_3{\Vert {\mathcal{L}}^{*}\Vert }_{\infty }^2}{{\Vert \hat{\mathcal{L}}-{\mathcal{L}}^{*}\Vert }_F^2}\right)$.

我们比较了T-HTN和TRPCA [1] 在数值实验上的恢复精度和运行速度，选取图片大小为 $300\times 300\times 3$，椒盐噪声为30%的彩色图片。通过与原始图片进行对比，得到张量去噪模型的恢复效果。下面给出在单张彩色图片上两种模型恢复效果的比较，如图1所示。同时，为了准确比较两种算法的恢复效果，采用PSNR来衡量两种模型在相同噪声下的恢复情况。其中，PSNR值越高，噪声数据恢复的效果越好，具体数据如表2所示。

Figure 1. Comparison of denoising effects between T-HTN and TRPCA

图1. T-HTN和TRPCA去噪效果对比

Table 2. T-HTN and TRPCA recover the PSNR values and running time data of the picture

表2. T-HTN和TRPCA恢复图片的PSNR值和运行时间数据

通过图1可以看出，本文提出的T-HTN模型在对被噪声污染的图片进行恢复时更接近与原始彩色图片，这也就说明了，截断核范数和截断Frobenius范数的方法可以有效的去除较大的奇异值对图像恢复的影响。表2的数据结果显示，在相同的噪声情况下，T-HTN模型恢复彩色图片时的PENR值普遍高于TRPCA，并且在迭代时间上要优于TRPCA模型。经过总体比较，T-HTN模型可以较准确地恢复彩色图片。

5. 结论

在本文，我们提出了混合张量截断核范数和截断张量Frobenius范数的张量鲁棒主成分分析模型，用一种简单的增广拉格朗日乘子法对模型进行求解。并用Matlab软件进行数值实验，经实验验证，本文提出的T-HTN模型可以有效恢复噪声图片，且恢复具有稳定性。

基金项目

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

NOTES

^*通讯作者。