一个三阶张量的稀疏分解方法及其应用

A Sparse Factorization Strategy for Third-Order Tensors and Its Application

摘要: 本文主要研究张量的分解算法及其应用。在张量的T-SVD算法的基础上提出TST-SVD算法，并且解决了T-SVD算法在分解时可能无法保留其主要信息的情况。而我们的TST-SVD则通过软阈值的方法可以很好地保留其主要信息，并且对于噪音图片也可以达到很好去噪效果。在图片的识别和重构方面也有着不错的表现。

Abstract: This paper mainly studies the decomposition algorithm of tensor and its application. TST-SVD al-gorithm is proposed on the basis of T-SVD algorithm of tensor, and it solves the case that the T-SVD algorithm may not be able to retain its main information when decomposing. However, our TST-SVD can keep its main information well through the soft threshold method, and achieve a good denoising effect for noise images. It also has a good performance in image recognition and reconstruction.

1. 引言

张量分解早在19世纪就被提出来了，随着计算机的发展张量活跃在各个领域。例如在神经影像，信号处理，化学统计学，计算机视觉，心理测验学，数据挖掘，图像处理等领域有着极其重要的应用。由于数据的复杂性以及我们所需要的一些特征，这就需要我们研究张量的内部结构特征。张量的经典分解有CP分解 [2]和Tucker分解 [2]，CP分解表示为由一系列秩一的向量外积之和，Tucker表示一个核张量 [2]与因子矩阵的n模积。

Tamara G. Kold和Brett W. Bader在2007发表了一篇关于张量的分解和应用的综述 [2]，文章讲解了什么是张量，如何做张量分解以及张量的一些应用。文章也提到了经典的CP分解和Tucker分解，也列举了其他的一些分解方法，并且用对比试验分析了它们的优缺点，给予研究人员很大的启发。Genevera I. Allen [3]提出了一种稀疏的CP分解算法，基于张量乘积的稀疏CP分解算法，创新性的使用软阈值操作以达到分解成分稀疏的效果。Eric C. Chi和Tamara G. Kolda [4]提出了基于泊松分布的张量分解模型，利用非线性Gauss-Seidel来构造优化函数加入一些约束条件得出KKT条件求得最优解。经过迭代到收敛得出新的稀疏非负的分解。Will Wei Sun [5]等人在Genevera I. Allen在稀疏CP分解的基础上提出了截断的张量CP分解，也取得了不错的效果。Misha E. Kilmer [1]等人提出了对张量做矩阵操作的张量T-SVD分解方法。这些算法在不同情况下已经被证实可以取得不错的效果。

这篇文章中我们提出了一个新的张量分解TST-SVD，它是在Misha E. Kilmer等人的基础上对其算法缺点做了修改并且实验结果也达到了预期的效果。针对T-SVD算法中直接对重构张量进行压缩处理而导致某些重要信息缺失的情况，我们对分解出的成分做软阈值操作以达到稀疏效果和保留重要信息的作用。

本文的组织结构如下：第2章介绍张量；第3章介绍张量的T-SVD并且详细讨论T-SVD算法及其总流程；第4章详细讲解我们新的算法(TST-SVD)；第5章为实验设置和结果分析；第6章总结全文。

2. 张量

张量是一个多维数组 [2]，一个零阶张量对应一个标量，一个一阶对应一个向量，一个二阶对应一个矩阵。一个三阶对应一个立方体 $A\in R^{I\times J\times K}$ 如图1，一个n阶张量表示为 $X\in R^{I_1\times I_2\times \cdots \times I_N}$ 。

Figure 1. Third order tensor $A\in R^{I\times J\times K}$

图1. 3阶张量 $A\in R^{I\times J\times K}$

Figure 2. Slices of a 3rd-ordertensor

图2. 3阶张量的切片

向量的第i个元素表示为 $a_i$ ，矩阵的第 $\left(i,j\right)$ 个元素表示为 $a_{ij}$ ，同样三阶张量的第 $\left(i,j,k\right)$ 个元素可以表示为 $a_{ijk}$ ，高阶张量以此类推。

张量的切片如图2所示。

3. 张量的T-SVD分解

它是在傅里叶域中一种基于矩阵的新的分解形式，类似与矩阵的奇异值分解他们有一些相似的性质。这对于张量是一个很实用的方法。

张量的T-SVD分解，A是一个 $n_1\times n_2\times n_3$ 的实数张量，则A可以表示为：

$A=U\ast S\ast V^{\text{T}}$ (1)

3.1. 定义1

由张量frontal切片组成的块循环矩阵：

$\text{circ}\left(A\right)=\left[\begin{array}{ccccc}{A}^{\left(1\right)}& A^{\left(n_3\right)}& A^{\left(n_3-1\right)}& \cdots & A^{\left(2\right)}\\ A^{\left(2\right)}& A^{\left(1\right)}& A^{\left(n_3\right)}& \cdots & A^{(3)}\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ A^{\left(n_3\right)}& A^{\left(n_3-1\right)}& \cdots & A^{\left(2\right)}& A^{\left(1\right)}\end{array}\right]$ (2)

其中 $A\in R^{n_1\times n_2\times n_3}$ 的张量， $A^{\left(i\right)}$ 是张量A的 $n_1\times n_2$ 的frontal切片， $\text{circ}\left(A\right)$ 是一个 $n_1{n}_3\times n_2{n}_3$ 的块循环矩阵。

我们定义MatVec操作， $\text{MatVec}\left(A\right)$ 的作用是把 $n_1\times n_2\times n_3$ 的张量变成了一个 $n_1{n}_3\times n_2{n}_3$ 的块矩阵，fold操作是对MatVec的一个还原。两个操作如下：

$\text{MatVec}\left(A\right)=\left[\begin{array}{c}{A}^{\left(1\right)}\\ A^{\left(2\right)}\\ ⋮\\ A^{\left(n_3\right)}\end{array}\right],\text{fold}\left(\text{MatVec}\left(A\right)\right)=A$ (3)

3.2. 定义2

我们来定义一个张量的t-product：

$A\ast B=\text{fold}\left(\text{circ}\left(A\right)\cdot \text{MatVec}\left(B\right)\right)$ (4)

其中 $A\in R^{n_1\times n_2\times n_3}$ ， $B\in R^{p\times n_2\times n_3}$ 。

3.3. 傅里叶变换

前面我们对矩阵做了一些操作使其具备了某些性质：块矩阵可以通过傅里叶变换变成块对角矩阵。这就意味着，当 $A\in R^{n_1\times n_2\times n_3}$ ，F是一个正则化的 $n_3\times n_3$ 的DFT (Discrete Fourier Transform)矩阵，则存在 $n_3$ 个 $n_1\times n_2$ 的矩阵 $D_i$ 使得：

$\left(F\otimes I\right)\text{circ}\left(A\right)\left(F^{*}\otimes I\right)=\text{blockdiag}\left(D_1,D_2,\cdots ,D_{n_3}\right)$ (5)

3.4. 张量的T-SVD

当张量是f-diagonal (对角)时，则他的每个frontal slice都是对角的。同样地，当张量是f-upper triangular或f-lower triangular时，则张量的frontal slice是上三角或者下三角。

定理1：A是一个 $n_1\times n_2\times n_3$ 的实数张量，则A的分解为：

$A=U\ast S\ast V^{\text{T}}$ (6)

其中 $U,V$ 分别是 $n_1\times n_2\times n_3$ 和 $n_2\times n_2\times n_3$ 的正交张量，S是一个 $n_1\times n_2\times n_3$ 的f-diagonal张量。这就是张量的T-SVD分解 [6]。

证明：首先我们把A变换成公式(2)的傅里叶域中，接着我们计算每个 $D_i$ 的SVD，则

$D_i=U_i{\Sigma }_i{V}_i^{\text{T}}\left(i=1,2,\cdots ,n_3\right)$

$\left[\begin{array}{ccc}{D}_i& & \\ & \ddots & \\ & & D_{n_3}\end{array}\right]=\left[\begin{array}{ccc}{U}_1& & \\ & \ddots & \\ & & U_{n_3}\end{array}\right]\left[\begin{array}{ccc}{\Sigma }_1& & \\ & \ddots & \\ & & {\Sigma }_{n_3}\end{array}\right]\left[\begin{array}{ccc}{V}_1^{\text{T}}& & \\ & \ddots & \\ & & V_{n_3}^{\text{T}}\end{array}\right]$ (7)

由公式(2)可得(6)式。

3.5. 张量的T-SVD的算法

算法1：

1) 输入 $n_1\times n_2\times n_3$ 的张量A。

2) 把A映射到傅里叶域中， $D=fft\left(A,\left[\right],3\right)$ 。

3) 对张量D的每一个frontal slice做矩阵的奇异值分解，得到的每个 $u,s,v$ 都分别存储在

$U\left(:,:,i\right),S\left(:,:,i\right),V\left(:,:,i\right)$ 中。

4) 在分别对 $U,S,V$ 做一个傅里叶逆变换。就可以得到张量A的奇异值分解。

3.6. 张量的T-SVD的截断定理

一个 $n_1\times n_2\times n_3$ 张量的A，它的T-SVD分解为 $A=U\ast S\ast V^{\text{T}}$ 。 $k<\min \left(n_1,n_2\right)$ ，则有

$A_k={\displaystyle \underset{i=1}{\overset{k}{\sum }}U\left(:,i,:\right)\ast S\left(i,i,:\right)\ast V{\left(:,i,:\right)}^{\text{T}}}$ (8)

3.7. 张量的T-SVD的截断算法

算法2：

1) 输入 $n_1\times n_2\times n_3$ 的张量A，截断k。

2) 用算法1得出 $U\left(:,i,:\right),S\left(i,i,:\right),V\left(:,i,:\right)$ 。

3) 分别计算 $U\left(:,i,:\right)$ 的 $k_1$ 个奇异值分解， $S\left(i,i,:\right)\ast V\left(:,i,:\right)$ 的 $k_2$ 个奇异值分解。

4) 计算 ${\sigma }_i{\mu }^{\left(j\right)}{\lambda }^{\left(l\right)}{\Vert \text{circ}\left(q^{\left(j\right)}\right)t^{\left(l\right)}\Vert }_{\infty }>\text{tol}$ [6]当满足条件时，可以得出张量A的截断T-SVD。

3.8. 新视角下的张量

我们定义两个操作squeeze和twist。

1) squeeze可以把张量矩阵化， $X:=\text{squeeze}\left(x\right)\Rightarrow X\left(i,j\right):=x\left(i,1,j\right)$ 。

2) twist把矩阵张量化， $\text{twist}\left(\text{squeeze}\left(x\right)\right)=x$ 。

其中 $x\in R^{n_1\times 1\times n_3}$ 。我们可以用它们来构造图片的张量矩阵，当M为图片的平均值矩阵，则 $A\left(:,j,:\right)=\text{twist}\left(X_j-M\right),j=1,\cdots ,m$ 。其中 $A\left(:,j,:\right)$ 是张量A的lateral slice， $X_j$ 是第j张图片。

4. 张量的TST-SVD算法

张量的TST-SVD是张量的T-SVD算法和张量的软阈值CP分解算法的基础上改进的。张量的TST-SVD在张量截断T-SVD算法的基础上合理的引入了软阈值操作。由于张量的T-SVD算法在去噪方面对于某些特征图片并没有很好地优化，因此加入了软阈值操作可以很好地平滑去噪。TST-SVD在人脸识别方面与传统的PCA和T-SVD相比有着较好的效果。

4.1. 软阈值操作

软阈值操作的公式为 $S\left(·,\rho \right)=\text{sign}(·)\left(|·|-\rho \right)+·$ [3]，

$U=\text{sign}\left(U\right)\left(\left|U\right|-{\rho }_U\ast I_U\right)+U$

$S=\text{sign}\left(S\right)\left(\left|S\right|-{\rho }_s\ast I_S\right)+S$

$V=\text{sign}\left(V\right)\left(\left|V\right|-{\rho }_V\ast I_V\right)+V$

其中 $\rho$ 是软阈值参数，在这里通过多次试验当 ${\rho }_U=0.001$ 时软阈值效果最好。I是元素全为1的张量并且与它们各自的规模相同。

4.2. 张量TST-SVD的算法步骤

算法3：

1) 输入 $n_1\times n_2\times n_3$ 的张量A，截断k。

2) 用算法1得出 $U\left(:,i,:\right),S\left(i,i,:\right),V\left(:,i,:\right)$ 。

3) 分别计算 $U\left(:,i,:\right)$ 的 $k_1$ 个奇异值分解， $S\left(i,i,:\right)\ast V\left(:,i,:\right)$ 的 $k_2$ 个奇异值分解。

4) 计算 ${\sigma }_i{\mu }^{\left(j\right)}{\lambda }^{\left(l\right)}{\Vert \text{circ}\left(q^{\left(j\right)}\right)t^{\left(l\right)}\Vert }_{\infty }>\text{tol}$ [6]当满足条件时，得出 $U,S,V$ 。

5) 分别对 $U,S,V$ 做软阈值 $S\left(·,\rho \right)$ 操作，得出最终的张量TST-SVD分解。

4.3. 张量TST-SVD在人脸识别上的算法步骤

由于U是正交的， $U_{\text{st}}$ 是U的正交集合。并且 $U_{\text{st}}\ast U_{\text{st}}^{\text{T}}$ 是一个正交投影，它把图片投影到更小的空间维度中。我们对张量A的lateralslice进行投影：

$A\left(:,j,:\right)\approx U_{\text{st}}\ast U_{\text{st}}^{\text{T}}\ast A\left(:,j,:\right)={\displaystyle \underset{t=1}{\overset{k}{\sum }}{U}_{\text{st}}\ast C\left(t,j,:\right)}$ (9)

其中 $C\left(:,j,:\right)=U_{\text{st}}^{\text{T}}\ast A\left(:,j,:\right)$ ，C就是我们图片投影的系数。当做人脸识别时，我们只需比较训练图片的投

影系数与测试图片的投影系数即可。

算法4：

1) 输入训练集图片 $I_i,i=1,2,\cdots ,N$ ；测试图片J。

2) 计算训练集图片的均值，得出均差图片 ${\varsigma }_i$ 。然后把每张图片以 ${\varsigma }_i\to A\left(:,i,:\right)$ 的形式存储到张量A的lateral slice中。

3) 由算法3得出U的软阈值 $U_{\text{st}}$ ， $U_{\text{st}}^{\text{T}}\ast A$ 表示训练集的正交投影。

4) 对测试图片做均值处理，再做一个 $\text{twist}\left(J-M\right)\to T\left(:,1,:\right)$ 的变换，对 $T\left(:,1,:\right)$ 做正交投影 $B\leftarrow U_{\text{st}}^{\text{T}}\ast T$ 得出测试图片的投影系数C。

5) 对测试图片的系数与训练图片的系数做2-范数，直到收敛。

6) 找出2-范数最小的那个就可以找出训练集图片的位置，从而达到识别的效果。

5. 实验设置和结果分析

为了比较张量的TST-SVD算法的性能，本文将TST-SVD算法，T-SVD算法和经典的PCA算法用于Yale faces [7]的人脸识别实验，并对实验结果进行结果对比分析。

5.1. 实验设置

我们选取10个不同的人，每个人有10种不同的表情，图片的大小是100 px × 100 px。第一组我们随机选取每个人的3个表情作为训练集的30张图片，剩下的70张图片作为测试集。第二组我们随机选取每个人的4个表情作为训练集的40张图片，剩下的60张图片作为测试集。第三组我们随机选取每个人的5个表情作为训练集的50张图片，剩下的50张图片作为测试集。第四组我们随机选取每个人的6个表情作为训练集的60张图片，剩下的40张图片作为测试集。第五组我们随机选取每个人的7个表情作为训练集的70张图片，剩下的30张图片作为测试集。分别使用上述的三种算法，针对每个组进行实验。并记录实验结果的人脸识别率和人脸重构的情况。实验平台为MATLAB R2014a。

5.2. 实验结果分析

为了使实验更加有效每组做20次实验所得的人脸识别率取平均值。其中人脸识别率等于识别正确的个数与测试集总数之比。在多次实验中TST-SVD的软阈值操作U的阈值为0.001时实验效果最好，在这里我们也取 ${\rho }_U=0.001$ (表1)。

我们再来比较TST-SVD与PCA的重构图片效果如何。重构图片的公式为： $J\approx U\ast U^{\text{T}}\ast J+M$ [8]。

由图3可以看出在相同训练集和测试集的情况下TST-SVD的识别率更高。图4可以看出在图片重构方面TST-SVD也有着不错的表现。

Table 1. The average face recognition probability of The TST-SVD, T-SVD and PCA

表1. TST-SVD，T-SVD和PCA的平均人脸识别率

Figure 3. Comparison of algorithm recognition rates of TST-SVD, T-SVD and PCA

图3. TST-SVD，T-SVD和PCA的算法识别率对比图

Figure 4. Comparison of reconstructed images of TST-SVD and PCA

图4. TST-SVD与PCA的重构图片对比图

6. 结语

原T-SVD算法的截断操作有可能会导致丢失重要的信息，而我们的TST-SVD算法找到了一种可以更好保留重要信息的能力，因为它加入了软阈值操作可以对重要信息进行平滑的去噪。在图像识别方面也取得了不错的效果。当重构图片时，加入软阈值之后的正交投影可以更好地重构图片的主要信息。在跟PCA算法做重构图片对比时，TST-SVD重构的图片明显比PCA更好。

致谢

文章感谢王丽娟老师在写作期间给予我的帮助和鼓励，感谢同门的陪伴和关怀。

参考文献