张量分解-Tucker分解

朴灿烈づ我的快乐病毒、 2022-06-05 07:36 638阅读 0赞

原文地址：[http://www.xiongfuli.com/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/2016-06/tensor-decomposition-tucker.html][http_www.xiongfuli.com_E6_9C_BA_E5_99_A8_E5_AD_A6_E4_B9_A0_2016-06_tensor-decomposition-tucker.html]

## Tucker分解 ##

Tucker的1966年文章中第一次提到了Tucker分解。一个三阶张量的Tucker分解的图示如下图所示。

![三阶张量的Tucker分解][Tucker]

对于一个三阶张量X∈RI×J×K X∈RI×J×K, 由Tucker分解可以得到A∈RI×P A∈RI×P,B∈RJ×Q B∈RJ×Q,C∈RK×R C∈RK×R三个因子矩阵和一个核张量 G∈RP×Q×R G∈RP×Q×R,每个mode上的因子矩阵称为张量在每个mode上的基矩阵或者是主成分,因此Tucker 分解又称为高阶PCA, 高阶SVD等。从图中可以看出，CP分解是Tucker分解的一种特殊形式：如果核张量的各个维数相同并且是对角的,则Tucker分解就退化成了CP分解。

在三阶张量形式中,有

X=G×1A×2B×3C=∑p=1P∑q=1Q∑r=1Rgpqrap∘bq∘cr=\[\[G;A,B,C\]\] X=G×1A×2B×3C=∑p=1P∑q=1Q∑r=1Rgpqrap∘bq∘cr=\[\[G;A,B,C\]\]

将上面的公式写成矩阵的形式即:

X1=AG(1)(C⊗B)TX2=BG(2)(C⊗A)TX3=CG(3)(B⊗A)T X1=AG(1)(C⊗B)TX2=BG(2)(C⊗A)TX3=CG(3)(B⊗A)T

对于三阶张量固定一个因子矩阵为单位阵，就得到Tucker分解一个重要的特例：Tucker2。例如固定 C=I C=I ，则退化为:

X=G×1A×2B=\[\[G;A,B,I\]\] X=G×1A×2B=\[\[G;A,B,I\]\]

进一步，如果固定两个因子矩阵，就得到了Tucker1例如固定 C=I C=I , B=I B=I ，则Tucker 分解就退化成了普通的PCA

X=G×1A=\[\[G;A,I,I\]\] X=G×1A=\[\[G;A,I,I\]\]

把上面的公式推广到 N N 阶的模型即可得到:

X=G×1A(1)×2A(2)⋯×(N)A(N)=\[\[G;A(1),A(2),⋯,A(N)\]\] X=G×1A(1)×2A(2)⋯×(N)A(N)=\[\[G;A(1),A(2),⋯,A(N)\]\]

写成矩阵形式即:

X(n)=A(n)G(n)(A(N)⊗⋯⊗A(n\+1)⊗A(n−1)⋯⊗A(1))T X(n)=A(n)G(n)(A(N)⊗⋯⊗A(n+1)⊗A(n−1)⋯⊗A(1))T

## n-秩与低秩近似 ##

n n\-秩又称为多线性秩。一个N阶张量X X的n-mode秩定义为：

rankn(X)=rank(X(n)) rankn(X)=rank(X(n))

令 rankn(X)=Rn,n=1,⋯,N rankn(X)=Rn,n=1,⋯,N 则 X X 叫做秩 (R1,R2,⋯,Rn) (R1,R2,⋯,Rn) 的张量。 Rn Rn 可以看作是张量 X X 在各个mode上fiber所构成的空间的维度。如果 rankn(X)=Rn,n=1,⋯,N rankn(X)=Rn,n=1,⋯,N ，则很容易得到 X X 的一个精确秩- (R1,R2,⋯,RN) (R1,R2,⋯,RN) Tucker分解；然而如果至少有一个  n n  使得  rankn(X)>Rn rankn(X)>Rn ，则通过Tucker分解得到的就是 X X 的一个秩-  (R1,R2,⋯,RN) (R1,R2,⋯,RN) 近似。下图展示了一个三阶张量的低秩近似,这个在图像处理中有可以认为是干净的图像。 ![三阶张量的低秩近似][tuckerLowRank.png]

## Tucker分解的求解 ##

对于固定的n n\-秩，Tucker分解的唯一性不能保证，一般加上一些约束，如分解得到的因子单位正交约束等。比如HOSVD(High Order SVD)求解算法,它通过张量的每一个mode上做SVD分解对各个mode上的因子矩阵进行求解,最后计算张量在各个mode上的投影之后的张量作为核张量。它的算法过程如下图所示。![HOSVD][]

虽然利用SVD对每个mode做一次Tucker1分解,但是HOSVD 不能保证得到一个较好的近似，但HOSVD的结果可以作为一个其他迭代算法（如HOOI）的很好的初始化。(\\textit\{High-order orthogonal iteration\})HOOI算法,将张量分解看作是一个优化的过程,不断迭代得到分解结果。假设有一个N N 阶张量X∈RI1×I2×⋯×IN X∈RI1×I2×⋯×IN,那么对X X进行分解就是对下面的问题进行求解:

∣∣X−\[\[G;A(1),⋯,A(N)\]\]∣∣ =∣∣vec(X)−(A(N)⊗⋯⊗A(1))vec(G)∣∣   |X−\[\[G;A(1),⋯,A(N)\]\]| =|vec(X)−(A(N)⊗⋯⊗A(1))vec(G)|

将上述的目标函数进一步化简得到:

∥∥X−\[\[G;A(1),⋯,A(N)\]\]∥∥2 =∥X∥2−2⟨X,\[\[G;A(1),⋯,A(N)\]\]⟩\+∣∣\[\[G;A(1),⋯,A(N)\]\]∣∣2 =∥X∥2−2⟨X×1A(1)T⋯×NA(N)T,G⟩\+∥G∥2 =∥X|2−2⟨G,G⟩\+∥G∥2   ‖X−\[\[G;A(1),⋯,A(N)\]\]‖2 =‖X‖2−2⟨X,\[\[G;A(1),⋯,A(N)\]\]⟩+|\[\[G;A(1),⋯,A(N)\]\]|2 =‖X‖2−2⟨X×1A(1)T⋯×NA(N)T,G⟩+‖G‖2 =‖X|2−2⟨G,G⟩+‖G‖2

而 G G 满足

G=X×1A(1)T⋯×NA(N)T G=X×1A(1)T⋯×NA(N)T

从而可与可以得到:

=∥X∥2−∥∥X×1A(1)T⋯×NA(N)T∥∥2 =‖X‖2−‖X×1A(1)T⋯×NA(N)T‖2

由于 ∥X∥ ‖X‖ 是一个常数,最小化上面的式子相当于最大化:

max∥∥X×1A(1)T⋯×NA(N)T∥∥subjecttoA(n)∈In×Rnandcolumnwiseorthogonal max‖X×1A(1)T⋯×NA(N)T‖subjecttoA(n)∈In×Rnandcolumnwiseorthogonal

写成矩阵形式即:

max∥∥A(n)TW∥∥ s.t. W=X(n)(A(N)⊗⋯⊗A(n\+1)⊗A(n−1)⋯⊗A(1)) max‖A(n)TW‖ s.t. W=X(n)(A(N)⊗⋯⊗A(n+1)⊗A(n−1)⋯⊗A(1))

这个问题可以通过令 A(n) A(n)  为  W W  的前  Rn Rn  个左奇异值向量来进行求解。HOOI算法的过程如下图所示。 ![HOOI algorithm][]

## 约束Tucker的分解 ##

除了可以在Tucker分解的各个因子矩阵上加上正交约束以外,还可以加一些其它约束,比如稀疏约束,平滑约束,非负约束等。另外在一些应用的场景中不同的mode的物理意义不同，可以加上不同的约束。在下图中在三个不同的mode上分别加上了正交约束,非负约束以及统计独立性约束等。![HOOI algorithm][HOOI algorithm 1]

## Tucker的分解的应用 ##

前面我们说Tucker分解可以看作是一个PCA的多线性版本,因此可以用于数据降维,特征提取,张量子空间学习等。比如说一个低秩的张量近似可以做一些去噪的操作等。Tucker分解同时在高光谱图像中也有所应用，如用低秩Tucker分解做高光谱图像的去噪,用张量子空间做高光谱图像的特征选择,用Tucker分解做数据的压缩等。下面以高光谱图像去噪为例作相关的介绍。 [http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=6909773][http_ieeexplore.ieee.org_xpls_abs_all.jsp_arnumber_6909773]中对高光谱图像去噪的流程如下图所示，![HOOI algorithm][HOOI algorithm 2]它首先对高光谱图像进行分块，然后对分的快进行聚类，得到一些group，最后对各个group里面的数据进行低秩Tucker分解。处理之前的噪声图像和处理之后的图像的对比如下图所示,可以发现Tucker分解可以对高光谱数据做有效的去噪处理。![有噪声图像][tuckerNoisy.png]![处理之后的图像][tuckerClean.png]

[http_www.xiongfuli.com_E6_9C_BA_E5_99_A8_E5_AD_A6_E4_B9_A0_2016-06_tensor-decomposition-tucker.html]: http://www.xiongfuli.com/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/2016-06/tensor-decomposition-tucker.html
[Tucker]: /images/20220605/beed6fcac8304ab0b47e0d1c9080698a.png
[tuckerLowRank.png]: /images/20220605/01e5ac299a5a479ba09d1fbf54114c26.png
[HOSVD]: /images/20220605/42f9f22e96594a69b04762f7d24a4dd3.png
[HOOI algorithm]: /images/20220605/368fba86a1f6437190b2ecf4cdbe8829.png
[HOOI algorithm 1]: /images/20220605/0f0adf5480744117a53ce482ce09f849.png
[http_ieeexplore.ieee.org_xpls_abs_all.jsp_arnumber_6909773]: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6909773
[HOOI algorithm 2]: http://www.xiongfuli.com/assets/img/201606/subspace.png
[tuckerNoisy.png]: http://www.xiongfuli.com/assets/img/201606/tuckerNoisy.png
[tuckerClean.png]: /images/20220605/6e268254e5fe4e70922b76b7558d948d.png