Tucker 分解

Tucker 分解

---

       Tucker 分解法可以被视作一种高阶 PCA. 它将张量分解为核心张量在每个mode上与矩阵的乘积. 因此, 对三阶张量 $\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$ ，我们有如下分解：
$$\mathcal{X}\approx \mathcal{G}{\times }_1\mathrm{A}{\times }_2\mathrm{B}{\times }_3\mathrm{C}=\sum _{p=1}^P\sum _{q=1}^Q\sum _{r=1}^R{g}_{pqr}{\mathrm{a}}_p\circ {\mathrm{b}}_q\circ {\mathrm{c}}_r=[[\mathcal{G};A,B,C]]$$

其中，$\mathrm{A}\in {\mathbb{R}}^{I\times P}$，$\mathrm{B}\in {\mathbb{R}}^{J\times Q}$ 和 $\mathrm{C}\in {\mathbb{R}}^{K\times R}$ 被称为因子矩阵，它们通常是正交的，可以视为沿相应 mode 下的主成分。张量 $\mathcal{G}\in {\mathbb{R}}^{P\times Q\times R}$ 被称为核心张量，其每个数字元素代表了不同成分之间的互动程度。三阶张量的 Tucker 分解可以用下图表示：

对于每个元素来说，Tucker 分解法可以写作
$$x_{ijk}\approx \sum _{p=1}^P\sum _{q=1}^Q\sum _{r=1}^R{g}_{pqr}{a}_{ip}{b}_{jq}{c}_{kr},i=1,\dots ,I,j=1,\dots ,J,k=1,\dots ,K$$

其中，$P,Q,R$ 为对应因子矩阵里列的个数。

       容易看出 CP 分解是 Tucker 分解的一种特殊形式，如果核心张量的为超对角张量而且 $P=Q=R$ ，Tucker 分解就退化成了权重 CP 分解。

       Tucker 分解可以写成如下的矩阵化形式：
$${\mathrm{X}}_{(1)}\approx \mathrm{A}{\mathrm{G}}_{(1)}(\mathrm{C}\otimes \mathrm{B}{)}^{\mathsf{T}}$$

$${\mathrm{X}}_{(2)}\approx \mathrm{B}{\mathrm{G}}_{(2)}(\mathrm{C}\otimes \mathrm{A}{)}^{\mathsf{T}}$$

$${\mathrm{X}}_{(3)}\approx \mathrm{C}{\mathrm{G}}_{(3)}(\mathrm{B}\otimes \mathrm{A}{)}^{\mathsf{T}}$$

Tucker 分解的高维推广

       对于 $N$ 维张量，Tucker 分解可以写作：
$$\mathcal{X}=\mathcal{G}{\times }_1{\mathrm{A}}^{(1)}{\times }_2{\mathrm{A}}^{(2)}\cdots {\times }_N{\mathrm{A}}^{(N)}=[[\mathcal{G};{\mathrm{A}}^{(1)},{\mathrm{A}}^{(2)},\dots ,{\mathrm{A}}^{(N)}]]$$

矩阵化可以写为：
$${\mathrm{X}}_{(n)}={\mathrm{A}}^{(n)}{\mathrm{G}}_{(n)}({\mathrm{A}}^{(N)}\otimes \cdots \otimes {\mathrm{A}}^{(n+1)}\otimes {\mathrm{A}}^{(n-1)}\otimes \cdots \otimes {\mathrm{A}}^{(1)}{)}^{\mathsf{T}}$$

Tucker 2 分解法

       对于三阶张量，固定一个因子矩阵为单位矩阵，就可以得到 Tucker 分解的一个重要的特例，Tucker 2 分解。例如，固定 $\mathrm{C}=\mathrm{I}$，若 $\mathrm{I}$ 是 $K\times K$ 的单位矩阵，则再使 $\mathcal{G}\in {\mathbb{R}}^{P\times Q\times R}$，那么我们就可以得到：
$$\mathcal{X}\approx \mathcal{G}{\times }_1\mathrm{A}{\times }_2\mathrm{B}=[[\mathcal{G};\mathrm{A},\mathrm{B},\mathrm{I}]]$$

Tucker 1 分解法

       更近一步，如果我们固定两个因子矩阵，只利用一个矩阵来分解，并将剩余矩阵设为单位矩阵。例如，如果设 $\mathrm{B}=\mathrm{C}=\mathrm{I}$，那么我们可以得到：
$$\mathcal{X}\approx \mathcal{G}{\times }_1\mathrm{A}=[[\mathcal{G};\mathrm{A},\mathrm{I},\mathrm{I}]]$$

这等价于一个标准的二维 PCA ，即：
$${\mathrm{X}}_{(1)}=\mathrm{A}{\mathrm{G}}_{(1)}$$

n - rank (n 秩)

       若 $\mathcal{X}$ 是一个大小为 $I_1\times I_2\times \cdots \times I_N$ 的 $N$ 阶张量，那么它的 n 秩为：$\mathcal{X}$ 在 mode - n 矩阵化后得到的矩阵 ${\mathrm{X}}_{(n)}$ 的列秩，表示为 ${\text{rank}}_n(\mathcal{X})$ 。如果在 Tucker 分解中，令
$$R_n={\text{rank}}_n(\mathcal{X}),n=1,2,\cdots ,N$$

那么就称张量 $\mathcal{X}$ 是一个 $\text{rank}-(R_1,R_2,\dots ,R_N)$ 张量。

       如果一个张量是 $\text{rank}-(R_1,R_2,\dots ,R_N)$ 张量，那么我们很容易找到一个 $R_n={\text{rank}}_n(\mathcal{X})$ 的精确 Tucker 分解。但是如果我们计算某些 $n$ 满足 $R_n<{\text{rank}}_n(\mathcal{X})$ 的 Tucker 分解，那么我们将必然无法获得精确的结果，即该分解不能精确地还原 $\mathcal{X}$ 。

Tucker 分解法的计算

1. HOSVD （高阶 SVD）

        该方法是利用 SVD 对每个 mode 做一次 Tucker 1 分解，其结果为将一个张量分解为一个核心张量和三个正交矩阵，HOSVD 是 Tucker 分解的一种特殊情况，其要求分解得到的因子矩阵必须为正交的，即
$$\mathcal{X}=\mathcal{G}{\times }_1{\mathrm{U}}_{(1)}{\times }_2{\mathrm{U}}_{(2)}{\times }_3{\mathrm{U}}_{(3)}$$

其中，$U_{(1)},U_{(2)},U_{(3)}$ 分别为先将张量进行 mode - n 矩阵化，得到 ${\mathcal{X}}_{(n)}$ 矩阵，然后对得到的矩阵进行奇异值分解，使得
$${\mathcal{X}}_{(n)}=U_{(n)}\Sigma V_{(n)}^T$$

对于不同的 mode 矩阵 ${\mathcal{X}}_{(n)}$ ，我们可以得到上面的式子中的 $U_{(n)}$ ，如果对三个 mode 矩阵都做上式的运算，就可以得到 $U_{(1)},U_{(2)},U_{(3)}$ 。

       根据
$$\mathcal{X}=\mathcal{G}{\times }_1{\mathrm{U}}_{(1)}{\times }_2{\mathrm{U}}_{(2)}{\times }_3{\mathrm{U}}_{(3)}$$

我们可以得到：
$$\mathcal{G}=\mathcal{X}{\times }_1{\mathrm{U}}_{(1)}^T{\times }_2{\mathrm{U}}_{(2)}^T{\times }_3{\mathrm{U}}_{(3)}^T$$

从而我们得到 HOSVD 的分解结果，即 $\mathcal{G},U_1,U_2,U_3$ 。

       如果至少存在一个 $R_n<{\text{rank}}_n(\mathcal{X})$ ，则称为截断 HOSVD 。

       HOSVD 不能保证得到一个较好的近似，但是 HOSVD 的结果可以作为一个其他迭代算法（如下面的 HOOI）的很好的初始解。

HOSVD 的另一种描述

我们定义一个张量 $G$ 的 键约化矩阵 为
$$J_{i{i}^{\prime }}=\sum _{jk}{G}_{ijk}{G}_{i^{\prime }jk}$$

由此我们可以引出对 $T$ 进行 HOSVD 算法的另外一种求解方法：

1. 计算各个指标的键约化矩阵
   $$I_{i{i}^{\prime }}=\sum _{jk}{T}_{ijk}{T}_{i^{\prime }jk}$$

   $$J_{j{j}^{\prime }}=\sum _{ik}{T}_{ijk}{T}_{i{j}^{\prime }k}$$

   $$K_{k{k}^{\prime }}=\sum _{ij}{T}_{ijk}{T}_{ij{k}^{\prime }}$$

2. 计算每个键约化矩阵的本征值分解
   $$I=U\Omega U^T$$

   $$J=V\Pi V^T$$

   $$K=W{\rm Y}{W}^T$$

3. 计算核张量
   $$G_{ijk}=\sum _{abc}{T}_{abc}{U}_{ai}{V}_{bj}{W}_{ck}$$

4. 得到高阶奇异值分解
   $$T_{abc}=\sum _{ijk}{G}_{ijk}{U}_{ai}{V}_{bj}{W}_{ck}$$

2. HOOI 迭代算法

       HOOI 秩去计算 ${\mathrm{X}}_{(n)}$ 的主奇异向量，并且运用 SVD 来代替特征值分解，或者只计算其主子空间的单位正交基底向量即可。

       设 $\mathcal{X}$ 是一个 $I_1\times I_2\times \cdots \times I_N$ 尺寸的张量，那么我们可以将要分解问题转化为求：
$$\min \left|\right|\mathcal{X}-[[\mathcal{G};{\mathrm{A}}^{(1)},{\mathrm{A}}^{(2)},\dots ,{\mathrm{A}}^{(N)}]]\left|\right|$$

其中，$\mathcal{G}\in {\mathbb{R}}^{R_1\times R_2\times \cdots \times R_N}$ ，矩阵 ${\mathrm{A}}^{(n)}\in {\mathbb{R}}^{I_n\times R_n}$ 且列正交。

对于上式的最优解，显然其核心张量 $\mathcal{G}$ 必须满足
$$\mathcal{G}=\mathcal{X}{\times }_1{\mathrm{A}}^{(a)\mathsf{T}}{\times }_2{\mathrm{A}}^{(2)\mathsf{T}}\cdots {\times }_N{\mathrm{A}}^{(N)\mathsf{T}}$$

则目标函数的平方为：
$$\begin{array}{rl}& \left|\right|\mathcal{X}-[[\mathcal{G};{\mathrm{A}}^{(1)},(2),\dots ,{\mathrm{A}}^{(N)}]]|{|}^2\\ & =||\mathcal{X}{||}^2-2⟨\mathcal{X},[[\mathcal{G};{\mathrm{A}}^{(1)},{\mathrm{A}}^{(2)},\dots ,{\mathrm{A}}^{(N)}]]⟩+||\mathcal{G};{\mathrm{A}}^{(1)},{\mathrm{A}}^{(2)},\dots ,{\mathrm{A}}^{(N)}{||}^2\\ & =||\mathcal{X}{||}^2-2⟨\mathcal{X}{\times }_1{\mathrm{A}}^{(1)\mathsf{T}}\cdots {\times }_N{\mathrm{A}}^{(N)\mathsf{T}},\mathcal{G}⟩+||\mathcal{G}{||}^2\\ & =||\mathcal{X}{||}^2-2⟨\mathcal{G},\mathcal{G}⟩+||\mathcal{G}{||}^2\\ & =||\mathcal{X}{||}^2-||\mathcal{G}{||}^2\\ & =||\mathcal{X}{||}^2-||\mathcal{X}{\times }_1{\mathrm{A}}^{(1)\mathsf{T}}{\times }_2\cdots {\times }_N{\mathrm{A}}^{(N)\mathsf{T}}{||}^2\end{array}$$

如果使目标函数取值最小，那么我们可以使得上面结果的第二项取最大值，即
$$\max \left|\right|\mathcal{X}{\times }_1{\mathrm{A}}^{(1)\mathsf{T}}{\times }_2{\mathrm{A}}^{(2)\mathsf{T}}\cdots {\times }_N{\mathrm{A}}^{(N)\mathsf{T}}\left|\right|$$

进一步，我们可以将上式写为
$$\max \left|\right|{\mathrm{A}}^{(n)\mathsf{T}}\mathrm{W}\left|\right|$$

其中
$$\mathrm{W}={\mathrm{X}}_{(n)}({\mathrm{A}}^{(N)}\otimes \cdots \otimes {\mathrm{A}}^{(n+1)}\otimes {\mathrm{A}}^{(n-1)}\otimes \cdots \otimes {\mathrm{A}}^{(1)})$$

我们可以将 $A^{(n)}$ 定义为 $\mathrm{W}$ 的前 $R_n$ 个左奇异向量就可以求出解。