Tensor Decomposition(Factorization).

张量分解（tensor decomposition/factorization）的思想是找到一个低秩结构近似原始数据张量。常用的方法包括：

1. Tucker分解
2. CP分解
3. 应用：缺失数据修复

1. Tucker分解

Tucker分解（Tucker decomposition）是一种高阶的主成分分析形式。它将一个张量分解成一个较小的核张量与一系列矩阵（二维张量）的乘积。

通常，给定一个三阶张量$x \in \Bbb{R}^{M×N×T}$，使用低秩（$R_1,R_2,R_3$）的Tucker分解可以表示为：

其中$g \in \Bbb{R}^{R_1×R_2×R_3}$是核张量（core tensor），$A \in \Bbb{R}^{M×R_1}$、$B \in \Bbb{R}^{N×R_2}$和$C \in \Bbb{R}^{T×R_3}$是因子矩阵（factor matrix）。

对于张量$X$的任意第($m,n,t$)个元素，Tucker分解也可以写作：

使用Python的Numpy库可以便捷实现上述运算过程：

import numpy as np
def tucker_combine(core_tensor, mat1, mat2, mat3):
    return np.einsum('ijk, mi, nj, tk -> mnt', core_tensor, mat1, mat2, mat3)

Tucker分解可以使用交替最小二乘法（Alternating Least Square， ALS）求解。

在Tucker分解中，采用平方误差作为损失函数，最小化该损失函数求解最优的核张量和因子矩阵：

该优化问题的困难在于需要同时优化核张量和三个因子矩阵，一种解决方法是使用交替最小二乘法。

交替最小二乘法把优化问题划分成几个独立的子问题，交替地优化每个子问题的损失函数。对于Tucker分解，每次优化g、A、B、C其中的一个参数，保持其他三个参数不变。求解单一参数的子问题是一个凸优化问题。

下面以求解核张量g为例，说明交替最小二乘法的优化过程。

上述问题的解可以表达为：

同理，求解因子矩阵$A \in \Bbb{R}^{M×R_1}$的优化问题可以写作：

上述问题可以表示为：

其最小二乘解为：

同理，因子矩阵$B \in \Bbb{R}^{N×R_2}$和$C \in \Bbb{R}^{T×R_3}$的最小二乘解为：

Tucker分解的核张量一般具有很大的值，容易过拟合；通常在求解核张量g时引入l1或l2正则化增强分解对于数据的鲁棒性：

上述问题的解可以表达为：

2. CP分解

CP分解（CANDECOMP/PARAFAC decomposition）也是一种常见的张量分解方法。它将一个张量分解成一系列因子向量外积（outer product）的和。

通常，给定一个三阶张量$x \in \Bbb{R}^{M×N×T}$，CP分解可以表示为：

其中因子向量（factor vector）$a_r \in \Bbb{R}^{M}$、$b_r \in \Bbb{R}^{N}$、$c_r \in \Bbb{R}^{T}$是因子矩阵（factor matrix）$A \in \Bbb{R}^{M×R}$、$B \in \Bbb{R}^{N×R}$和$C \in \Bbb{R}^{T×R}$的第$r$列。实际上这些向量的外积是秩为$1$的张量，CP分解就是把原张量分解成$R$个秩为$1$的张量之和。

对于张量$x$的任意第($m,n,t$)个元素，CP分解也可以写作：

实际上，CP分解是Tucker分解的一种特殊形式，可以表示为：

其中核张量g是对角张量，即:

使用Python的Numpy库可以便捷实现上述运算过程：

import numpy as np
def cp_combine(mat1, mat2, mat3):
    return np.einsum('mr, nr, tr -> mnt', mat1, mat2, mat3)

在CP分解中，采用平方误差作为损失函数，最小化该损失函数求解最优的因子矩阵：

使用交替最小二乘法把该优化问题划分成几个独立的子问题，交替地优化每个子问题的损失函数。对于CP分解，每次优化A、B、C其中的一个参数，保持其他三个参数不变。求解单一参数的子问题是一个凸优化问题。

具体地，求解因子矩阵$A \in \Bbb{R}^{M×R}$的第$m$行$a_m \in \Bbb{R}^{R}$可以表示为：

其最小二乘解为：

同理，因子矩阵$B \in \Bbb{R}^{N×R}$的第$n$行$b_n \in \Bbb{R}^{R}$和因子矩阵$C \in \Bbb{R}^{T×R}$的第$t$行$c_t \in \Bbb{R}^{R}$的最小二乘解为：

3. 应用：缺失数据修复

张量分解可以用于修复缺失数据。

• 实例：时空交通数据缺失值修复

如下图所示，对于一个含有缺失数据的数据张量$Y$，对其进行张量分解，分解成一系列低秩张量的乘积。将这些低秩张量的乘积作为原数据张量的重构，修复其缺失值：