本文是对论文Tensor Decompositions and Applications进行了翻译、整理、筛选和适当的补充，如何希望深入理解可以阅读原文。

相关文章：

【张量分解(一)】符号与基础知识
【张量分解(二)】CP分解
【张量分解(三)】Tucker分解

一、CP分解

1.1 定义

CP分解就是将一个张量分解成多个单秩张量的和。例如，给定一个三阶张量$\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$，则CP分解可以写为
$$\mathcal{X}\approx \sum _{r=1}^R{\text{a}}_r\circ {\text{b}}_r\circ {\text{c}}_r$$
其中，$\circ$是指向量外积，$R$是正整数且${\text{a}}_r\in {\mathbb{R}}^I$,${\text{b}}_r\in {\mathbb{R}}^J$,${\text{c}}_r\in {\mathbb{R}}^K$。下图展示了三阶张量的CP分解

将上面的CP分解展开，也可以写作
$$x_{ijk}\approx \sum _{r=1}^R{a}_{ir}{b}_{jr}{c}_{kr},i=1,2,\dots ,I,j=1,2,\dots ,J,k=1,2,\dots ,K$$
此外，对于三阶张量来说，可以从通道切片(frontal slice)的角度表示CP分解
$${\text{X}}_k\approx \text{A}{\text{D}}^{(k)}{\text{B}}^T，{\text{D}}^{(k)}\equiv diag({\text{c}}_{k:}),k=1,\dots ,K$$
其中，${\text{X}}_k$表示张量$\mathcal{X}$的第k个通道切片。对于行切片和列切片也可以写出类似的公式。

1.2 张量矩阵化后的CP分解

在文章【张量分解(一)】符号与基础知识中介绍过张量的矩阵化。这里主要介绍将张量转换为矩阵后的CP分解。
首先，定义因子矩阵(factor matrices)为CP分解中组成单秩张量的同一维度的向量合并成的矩阵(这个表述有点绕)。具体来说，就是把所有的$\text{a}$向量合并成一个矩阵$\text{A}=[{\text{a}}_1{\text{a}}_2\dots {\text{a}}_R]$。同理，还可以合成因子矩阵$\text{B}$和$\text{C}$。那么矩阵化后的张量CP分解形式如下：
$${\text{X}}_{(1)}\approx \text{A}(\text{B}\odot \text{C}{)}^T$$
$${\text{X}}_{(2)}\approx \text{B}(\text{C}\odot \text{A}{)}^T$$
$${\text{X}}_{(3)}\approx \text{C}(\text{B}\odot \text{A}{)}^T$$
其中，$\odot$表示Khatri-Rao积，${\text{X}}_{(i)}$表示张量$\mathcal{X}$的模i矩阵化后的矩阵。

1.3 符号表示

为了更加简洁的表达，CP分解可以简写如下$$\mathcal{X}\approx ⟮\text{A},\text{B},\text{C}⟯$$
实在是打不出空心方括号(摊手)，只能用$⟮⟯$代替了。


通常，假设矩阵$\text{A}$,$\text{B}$和$\text{C}$的列向量是标准化后的向量，并且将提取出来的权重合并入向量$\lambda \in {\mathbb{R}}^R$，因此CP分解还可以写成$$\mathcal{X}\approx \sum _{r=1}^R{\lambda }_r{\text{a}}_r\circ {\text{b}}_r\circ {\text{c}}_r=⟮\lambda ;\text{A},\text{B},\text{C}⟯$$

1.4 高维扩展

先前主要介绍的是三阶张量的CP分解，主要是因为其具有广泛的适用性。对于N阶张量$\mathcal{X}\in {\mathbb{R}}^{I_1\times I_2\times \cdots \times I_N}$，其CP分解为
$$\mathcal{X}\approx \sum _{r=1}^R{\lambda }_r{\text{a}}_r^{(1)}\circ {\text{a}}_r^{(2)}\circ \cdots \circ {\text{a}}_r^{(N)}=⟮\lambda ;{\text{A}}^{(1)},{\text{A}}^{(2)},\dots ,{\text{A}}^{(N)}⟯$$
其中，$\lambda \in {\mathbb{R}}^R$且${\text{A}}^{(n)}\in {\mathbb{R}}^{I_n\times R},n=1,2,\dots ,N$

类似的，N阶张量$\mathcal{X}$进行模n矩阵化后的CP分解为
$${\text{X}}_{(n)}\approx {\text{A}}^{(n)}\mathrm{\Lambda }({\text{A}}^{(N)}\odot \cdots \odot {\text{A}}^{n+1}\odot {\text{A}}^{n-1}\odot \cdots \odot {\text{A}}^{(1)}{)}^T$$
其中，对角矩阵$\mathrm{\Lambda }=diag(\lambda )$。

二、张量的秩(Tensor Rank)

2.1 张量秩的定义

用于生成张量$\mathcal{X}$所需要的单秩张量的最小数量即为张量$\mathcal{X}$的秩，用$rank(\mathcal{X})$表示。换个角度，张量的秩就是CP分解时单秩张量数量的最小值。

2.2 张量秩与矩阵秩

此外，张量的秩与矩阵秩的定义非常相似，但是二值的性质非常的不同。例如，实数张量的秩在实数域$\mathbb{R}$和复数域$\mathbb{C}$上可能会不同。另一个张量秩和矩阵秩的显著不同是，当前没有一个直接的方法来确定给定张量的秩。例如，Krushkal对特定的$9\times 9\times 9$的张量进行分析，只能确定其秩在18到23之间。在实际应用中，张量的秩是通过CP分解来确定的。

2.3 张量的最大秩和典型秩

最大秩：一类张量能够达到的最大的秩称为张量的最大秩(maximum rank)。典型秩：一个从均匀连续分别中随机抽取元素所组成的张量中，出现概率大于0的任何秩。
具体来说，对于所有形状为$I\times J$的矩阵，最大秩和典型秩均等于 m i n { I , J } min\{I,J\} min{I,J}。但是对于张量来说，最大秩和典型秩可能不相同，而且典型秩可能不只一个。例如$2\times 2\times 2$张量的典型秩为2或3，通过蒙特卡洛实验也可以发现秩为2的张量占79%，秩为3的张量占21%，秩为1的张量在理论上虽然可能，但是实际概率为0。
对于一般的三阶张量$\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$，当前只知道其最大秩的一个弱上界
r a n k ( X ) ≤ m i n { I J , I K , J K } rank(\mathcal{X})\leq min\{IJ,IK,JK\} rank(X)≤min{IJ,IK,JK}
对于特定形状或类型的张量来说，有可能存在一些确定最大秩和典型秩的具体值或者范围的方法，可以参考原文Tensor Decompositions and Applications

三、唯一性

高阶张量的一个有趣的特性是它的秩分解是唯一的，而通常矩阵分解不是。

3.1 矩阵分解的不唯一性

对于秩为$R$的矩阵$\text{X}\in {\mathbb{R}}^{I\times J}$，其秩分解可以写为
$$\text{X}={\text{AB}}^T=\sum _{r=1}^R{\text{a}}_r\circ {\text{b}}_r$$
具体来说，对于矩阵$\text{X}$的SVD分解为${\mathrm{U}\mathrm{\Sigma }\mathrm{V}}^T$，为了与上面的秩分解对于，令$\text{A}=\mathrm{U}\mathrm{\Sigma }$且$\text{B}=\mathrm{V}$。但是，如果令$\text{A}=\mathrm{U}\mathrm{\Sigma }\mathrm{W}$且$\text{B}=\mathrm{V}\mathrm{W}$,其中$\mathrm{W}$是$R\times R$的正交矩阵($W^{T}W=E$)，同样也满足矩阵秩分解的定义。
换句话说，我们可以轻易的构造两个完全不同的单秩矩阵集合，但是集合中的矩阵相加就等于原始矩阵。而SVD分解的唯一性仅仅是因为正交约束的加入。

3.2 张量分解的唯一性

通常，在十分微弱的约束条件下，张量的CP分解就是唯一的。对于秩为$R$的三阶张量$\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$，其CP分解为
$$\mathcal{X}=\sum _{r=1}^R{\text{a}}_r\circ {\text{b}}_r\circ {\text{c}}_r=⟮\text{A},\text{B},\text{C}⟯$$
而唯一性就是指上面的分解中是唯一可能的单秩矩阵的组合。当然，这是排除了缩放和重新排列后的唯一性。例如这里使用置换矩阵对分解后的单秩矩阵的列进行重排列
$$\mathcal{X}=⟮\text{A},\text{B},\text{C}⟯=⟮\text{A}\Pi ,\text{B}\Pi ,\text{C}\Pi ⟯$$
其中，$\Pi$是$R\times R$的置换矩阵。同样，对于将CP分解中的向量进行缩放也不影响CP分解的结果，例如
$$\mathcal{X}=\sum _{r=1}^R({\alpha }_r{\text{a}}_r)\circ ({\beta }_r{\text{b}}_r)\circ ({\gamma }_r{\text{c}}_r)$$
其中，${\alpha }_r{\beta }_r{\gamma }_r=1,r=1,...,R$

3.3 CP分解唯一性的充分条件

对于CP分解$\mathcal{X}=⟮\text{A},\text{B},\text{C}⟯$，令$k_A$、$k_B$、$k_C$分别表示矩阵$\text{A}$、$\text{B}$、$\text{C}$的秩，那么CP分解唯一的充分条件是$$k_A+k_B+k_C\ge 2R+2$$
将上面的条件扩展至N维，对于张量$$\mathcal{X}=\sum _{r=1}^R{\text{a}}_r^{(1)}\circ {\text{a}}_r^{(2)}\circ \cdots \circ {\text{a}}_r^{(N)}=⟮{\text{A}}^{(1)},{\text{A}}^{(2)},\dots ,{\text{A}}^{(N)}⟯$$，其CP分解唯一性的充分条件为
$$\sum _{n=1}^N{k}_{{\text{A}}^{(n)}}\ge 2R+(N-1)$$

3.4 CP分解唯一性的必要条件

上面的充分条件在$R=2$或$R=3$的条件下，也是CP分解唯一性的必要条件，但是当$R>3$则不成立。更加广泛的CP分解唯一性的必要条件为
m i n { r a n k ( A ⊙ B ) , r a n k ( A ⊙ C ) , r a n k ( B ⊙ C ) } = R min\{rank(\textbf{A}\odot\textbf{B}),rank(\textbf{A}\odot\textbf{C}),rank(\textbf{B}\odot\textbf{C})\}=R min{rank(A⊙B),rank(A⊙C),rank(B⊙C)}=R
推广的N维情况下，则
$$mi{n}_{n=1,\dots ,N}rank({\text{A}}^{(1)}\odot \cdots \odot {\text{A}}^{(n-1)}\odot {\text{A}}^{(n+1)}\odot \cdots \odot {\text{A}}^{(N)})=R$$
但是，由于性质
$$rank(\text{A}\odot \text{B})\le rank(\text{A}\otimes \text{B})\le rank(\text{A})\cdot rank(\text{B})$$
因此，N维下的必要条件可以扩展为
$$mi{n}_{n=1,\dots ,N}(rank({\text{A}}^{(1)})\cdot \cdots \cdot rank({\text{A}}^{(n-1)})\cdot rank({\text{A}}^{(n+1)})\cdot \cdots \cdot rank({\text{A}}^{(N)}))\ge R$$

3.5 CP分解唯一性的判断标准

对于秩为$R$的三阶张量$\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$，当满足条件
$$R\le K并且R(R-1)\le I(I-1)J(J-1)/2$$
则，其CP分解是唯一的。
类似的，对于秩为R的四阶张量$\mathcal{X}\in {\mathbb{R}}^{I\times J\times K\times L}$，其CP分解唯一的条件是
$$R\le L并且R(R-1)\le IJK(3IJK-IJ-IK-JK-I-J-K+3)/4$$

四、低秩近似与边界秩(border rank)

4.1 矩阵的低秩近似

给定一个秩为$R$的矩阵$\text{A}$，那么该矩阵的SVD分解可以写作：
$$\text{A}=\sum _{r=1}^R{\sigma }_r{\text{u}}_r\circ {\text{v}}_r，其中{\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_R$$
那么该矩阵的秩k近似，可以直接使用SVD分解中前k个部分，即
$$\text{B}=\sum _{r=1}^k{\sigma }_r{\text{u}}_r\circ {\text{v}}_r$$

4.2 张量的低秩近似

上面对于矩阵的结果并不适用于张量。给定一个秩为$R$的三阶张量，其CP分解为
$$\mathcal{X}=\sum _{r=1}^R{\lambda }_r{\text{a}}_r\circ {\text{b}}_r\circ {\text{c}}_r$$
按上面矩阵的低秩近似来看，三阶张量的秩k近似也应该是其中k个部分的和，但实际情况并非如此。
Kolda提供过一个例子，对于一个三阶张量的单秩近似并不是秩2近似的组成部分(在矩阵的低秩分解中一定成立)。因此会得出一个推论，一个张量的最优秩k近似中的k个组成部分并不是按顺序求得的，而是需要同时被发现的。
总的来说，这个问题比较复杂，有时一个张量的最优秩k近似不一定存在。如果一个张量可以通过低秩的因式分解任意逼近，那么该张量就是一个退化张量。
举一个具体的例子来说，给定一个秩为3的具体三阶张量$\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$为
$$\mathcal{X}={\text{a}}_1\circ {\text{b}}_1\circ {\text{c}}_2+{\text{a}}_1\circ {\text{b}}_2\circ {\text{c}}_1+{\text{a}}_2\circ {\text{b}}_1\circ {\text{c}}_1$$
其中,$\text{A}\in {\mathbb{R}}^{I\times 2},\text{B}\in {\mathbb{R}}^{J\times 2},\text{C}\in {\mathbb{R}}^{K\times 2}$是由于上式中对应的向量组成的，且这三个矩阵的列向量线性无关。
上面描述的张量可以使用下面的下面的秩2张量进行任意的近似
$$\mathcal{Y}=n({\text{a}}_1+\frac{1}{n}{\text{a}}_2)\circ ({\text{b}}_1+\frac{1}{n}{\text{b}}_2)\circ ({\text{c}}_1+\frac{1}{n}{\text{c}}_2)-n{\text{a}}_1\circ {\text{b}}_1\circ {\text{c}}_1$$
原始的秩3张量$\mathcal{X}$和近似的秩2张量$\mathcal{Y}$之间的误差为
$$\Vert \mathcal{X}-\mathcal{Y}\Vert =\frac{1}{n}\Vert {\text{a}}_2\circ {\text{b}}_2\circ {\text{c}}_1+{\text{a}}_2\circ {\text{b}}_1\circ {\text{c}}_2+{\text{a}}_1\circ {\text{b}}_2\circ {\text{c}}_2+\frac{1}{n}{\text{a}}_2\circ {\text{b}}_2\circ {\text{c}}_2\Vert$$
当然，这个误差可以任意的小。

4.3 边界秩(border rank)

在不存在最优低秩近似的情况下，可以考虑边界秩。其定义为，能够以任意非零误差充分近似给定张量的最小单秩张量的数量。形式化的定义为
r a n k ~ ( X ) = m i n { r ∣ 对 于 任 意 ϵ > 0 , 均 存 在 一 个 张 量 E 满 足 ∥ E ∥ < ϵ 且 r a n k ( X + E ) = r } \widetilde{rank}(\mathcal{X})=min\{r|对于任意\epsilon>0,均存在一个张量\mathcal{E}满足\Vert\mathcal{E}\Vert<\epsilon且rank(\mathcal{X}+\mathcal{E})=r\} rank (X)=min{r∣对于任意ϵ>0,均存在一个张量E满足∥E∥<ϵ且rank(X+E)=r}
显然，$$\widetilde{rank}(\mathcal{X})\le rank(\mathcal{X})$$

五、计算CP分解

本小节介绍怎么计算一个张量的CP分解。
在前面的小节中提到过，没有一个有限的算法可以确定张量的秩。而CP分解则是将待分解张量分解成$R$个单秩张量，其中$R$就是待分解张量的秩。因此，计算CP分解的第一个问题就是如何确定张量的秩。
大多数的CP求解思路是尝试不同的$R$值来拟合待分解张量，直至找到一个最佳的分解。对于无噪声的数据，那么可以对$R$的值从1,2,…这样逐步尝试，从而得到一个最优的CP分解。但是，前面介绍了张量的低秩近似，一个张量可以被一个更低秩的张量任意逼近，这在实际中有一些问题。

5.1 计算三阶张量的CP分解

假设CP分解中的$R$取值已经确定，那么这里介绍一种求解CP分解的ALS(交替最小二乘法)算法。
令$\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$，该算法的目标是计算一个包含$R$个单秩张量的CP分解，使其尽量近似$\mathcal{X}$，即
$$mi{n}_{\hat{\mathcal{X}}}\Vert \mathcal{X}-\hat{\mathcal{X}}\Vert ,其中\hat{\mathcal{X}}=\sum _{r=1}^R{\lambda }_r{\text{a}}_r\circ {\text{b}}_r\circ {\text{c}}_r=⟮\lambda ;\text{A},\text{B},\text{C}⟯$$
交替最小二乘法(ALS)就是固定B和C，求解A；再固定A和C，求解B；再固定A和B，求解C。重复上面的过程，直至满足收敛条件。这就是ALS的思路。
固定两个张量来求解另外一个张量，这就变成了线性最小二乘的问题。例如，B和C固定，那么依照1.2节中张量矩阵化后的CP分解，那么就能把上面的最小化问题重写为
$$mi{n}_{\hat{\text{A}}}\Vert {\text{X}}_{(1)}-\hat{\text{A}}(\text{C}\odot \text{B}{)}^T{\Vert }_F,其中\hat{\text{A}}=\text{A}\cdot diag(\lambda )$$
上面的最小化问题的最优解为
$$\hat{\text{A}}={\text{X}}_{(1)}[(\text{C}\odot \text{B}{)}^T{]}^{-1}$$
其中，-1是指张量的伪逆，而Khatri-Rao积的伪逆可以进行变换，因此上面的最优解还可以写作
$$\hat{\text{A}}={\text{X}}_{(1)}(\text{C}\odot \text{B})({\text{C}}^T\text{C}\ast {\text{B}}^T\text{B}{)}^{-1}$$
这个版本写法的最优解有一个优势，仅需要求解一个$R\times R$矩阵的伪逆，而不是$JK\times R$矩阵的伪逆。最后，对矩阵$\hat{\text{A}}$的列进行标准化后就得到了矩阵$\text{A}$。

5.2 ALS算法在高维张量上的应用

给定N阶张量$\mathcal{X}\in {\mathbb{R}}^{I_1\times I_2\times \cdots \times I_N}$，使用CP分解将其分解为$R$个单秩矩阵的ALS算法。