Tucker 分解

张量分解-Tucker分解 2016.06.19

Tucker分解

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

Tucker 分解

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

在三阶张量形式中,有

 =  \times 1 A \times 2 B \times 3 C = \sum p = 1 P \sum q = 1 Q \sum r = 1 R g p q r a p \circ b q \circ c r = [[; A, B, C]] XG1A2B3Cp1Pq1Qr1RgpqrapbqcrGABC

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

X 1 = A G (1) (C \otimes B) T X 2 = B G (2) (C \otimes A) T X 3 = C G (3) (B \otimes A) T X1AG1CBTX2BG2CATX3CG3BAT

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

 =  \times 1 A \times 2 B = [[; A, B, I]] XG1A2BGABI

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

 =  \times 1 A = [[; A, I, I]] XG1AGAII

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

 =  \times 1 A (1) \times 2 A (2) \dots \times (N) A (N) = [[; A (1), A (2), \dots, A (N)]] XG1A12A2NANGA1A2AN

写成矩阵形式即:

X (n) = A (n) G (n) (A (N) \otimes \dots \otimes A (n + 1) \otimes A (n - 1) \dots \otimes A (1)) T XnAnGnANAn1An1A1T

n-秩与低秩近似

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

r a n k n () = r a n k (X (n)) ranknXrankXn

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

Tucker分解的求解

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

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

∣ ∣  - [[; A (1), \dots, A (N)]] ∣ ∣ = ∣ ∣ vec () - (A (N) \otimes \dots \otimes A (1)) vec () ∣ ∣ XGA1AN vecXANA1vecG

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

‖ ‖  - [[; A (1), \dots, A (N)]] ‖ ‖ 2 = ‖  ‖ 2 - 2 ⟨ , [[; A (1), \dots, A (N)]] ⟩ + ∣ ∣ [[; A (1), \dots, A (N)]] ∣ ∣ 2 = ‖  ‖ 2 - 2 ⟨  \times 1 A (1) T \dots \times N A (N) T,  ⟩ + ‖  ‖ 2 = ‖  | 2 - 2 ⟨ ,  ⟩ + ‖  ‖ 2 XGA1AN2 X22XGA1ANGA1AN2 X22X1A1TNANTGG2 X22GGG2

而G满足

 =  \times 1 A (1) T \dots \times N A (N) T GX1A1TNANT

从而可与可以得到:

= ‖  ‖ 2 - ‖ ‖  \times 1 A (1) T \dots \times N A (N) T ‖ ‖ 2 X2X1A1TNANT2

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

max ‖ ‖  \times 1 A (1) T \dots \times N A (N) T ‖ ‖ s u b j e c t t o A (n) \in ? ? \times ℝ ? a n d c o l u m n w i s e o r t h o g o n a l X1A1TNANTsubjecttoAnInRnandcolumnwiseorthogonal

写成矩阵形式即:

max ‖ ‖ A (n) T W ‖ ‖ s .t . W = X (n) (A (N) \otimes \dots \otimes A (n + 1) \otimes A (n - 1) \dots \otimes A (1)) AnTW s.t. WXnANAn1An1A1

这个问题可以通过令A(n)An 为 WW 的前 RnRn 个左奇异值向量来进行求解。HOOI算法的过程如下图所示。 Tucker 分解

约束Tucker的分解

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

Tucker的分解的应用

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