张量（二）：张量分解（tensor decomposition）

2023-11-11

与矩阵分解一样，我们希望通过张量分解去提取原数据中所隐藏的信息或主要成分。当前主流的张量分解方法有CP分解，Tucker分解，t-SVD分解等，更新的方法大多是在他们的基础上做进一步的改进或引用。因此，张量分解也是张量算法的基础。下面分别做介绍。

一、CP分解

二、Tucker分解

三、t-SVD分解

四、张量链分解

五、张量环分解

一、CP分解

CP分解是将任意高阶张量分解成多个秩为1的“因子张量”之和。如下图，每个因子张量的单个维度上秩都为1。若一个三维张量的数据为 $\textit{X} \in \mathbb{R}^{\mathit{I}\times \mathit{J}\times \mathit{K}}$ ，则其CP分解表达式为 $\mathit{X}=\sum_{r=1}^{R}a_{r}\circ b_{r}\circ c_{r}$ ，其中R为张量秩的大小，向量之间的乘积是外积的形式。虽然CP分解的表达式很简洁，但对其秩的求解却是一个NP-hard的问题，很难确定张量秩的大小。

CP分解模型图

二、Tucker分解

Tucker分解又名高阶奇异值分解（higher-order SVD，HOSVD）。众所周知，奇异值分解（SVD）是将矩阵分解为两个因子矩阵和一个奇异值对角矩阵，扩展到高阶领域就是将张量分解成一个核张量和多个正交因子矩阵的模式积。同时，CP分解是一种特殊的Tucker分解。示意图如下。

Tucker分解示意图

对一个N阶张量 $\mathit{X}\in \mathbb{R}^{\mathit{I_{1}\times \mathit{I_{2}\times \cdots \times \mathit{I_{N}}}}}$ ，Tucker分解表达式为 $\mathit{X}=\mathfrak{g}\times _{1}\mathbf{U}^{\left ( 1 \right )}\times_{2}\mathbf{U}^{\left ( 2 \right )}\cdots \times _{N}\mathbf{U}^{\left ( N \right )}$ 。Tucker分解中Tucker秩可以用核范数之和来近似表示，其定义为 $\sum _{k}\left \| \mathbf{X}_{\left ( k \right )} \right \|$ ，其中 $\left \| \mathbf{X}_{\left ( k \right )} \right \|$ 表示展开矩阵 $\mathbf{X}_{\left ( k \right )}$ 的奇异值之和。在分解模型图中，三个因子矩阵分别是三个不同空间对应的正交基，它们秩的大小决定了张量的Tucker秩。

Tucker分解可以用交替最小二乘法来求解。其基本思想是利用在第k次求出的因子矩阵 $\mathbf{U}_{k}^{\left ( i+1 \right )}\cdots \mathbf{U}_{k}^{\left ( N \right )}$ 和在第k+1次更新的因子矩阵 $\mathbf{U}_{k+1}^{\left ( 1 \right )}\cdots \mathbf{U}_{k+1}^{\left ( i-1 \right )}$ 来求解因子矩阵 $\mathbf{U}_{k+1}^{i}$ 的最小二乘解：

$\hat{\mathbf{U}}_{k+1}^{\left ( i \right )}=argmin\left \| \mathit{X}-f\left ( \mathbf{\mathbf{U}_{k+1}^{\left ( 1 \right )}\cdots \mathbf{U}_{k+1}^{\left ( i-1 \right )},\mathbf{U}^{\left ( i \right )},\mathbf{U}_{k}^{\left ( i+1 \right )}\cdots \mathbf{U}_{k}^{\left ( N \right )}} \right ) \right \|_{2}^{2}$

对于每次迭代和每个因子矩阵交替使用最小二乘法，直到满足算法的收敛准则。算法流程图如下。

HOSVD算法流程图

三、t-SVD分解

t-SVD分解是建立在新定义的张量积（t-product）基础上的新的分解框架，主要针对三维张量数据的分解。

张量积：对张量 $\mathit{A}\in \mathbb{R}^{\mathit{I}_{1}\times \mathit{I}_{2}\times \mathit{I}_{3}}$ 和 $\mathit{B}\in \mathbb{R}^{\mathit{I}_{2}\times \mathit{I}_{4}\times \mathit{I}_{3}}$ ，张量积定义为 $\boldsymbol{l}=\mathit{A}\ast \mathit{B}\in \mathbb{R}^{\mathit{I}_{1}\times \mathit{I}_{4}\times \mathit{I}_{3}}$ 。即不同形式展开矩阵之间的乘积：

$\boldsymbol{l}=\mathit{A}\ast \mathit{B}=fold\left ( circ\left ( \mathit{A} \right ) \cdot unfold\left ( \mathit{B} \right )\right )$ 。

等价于两个张量中管纤维之间的圆周卷积：

$\boldsymbol{l}\left ( i,j,: \right )= \sum_{k=1}^{n_{2}}\mathit{A}\left ( i,k,: \right )\bullet \mathit{B}\left ( j,k,: \right )$

这里的unfold和fold分别表示张量的展开和叠加操作，二者互为逆操作。circ()表示循环展开操作，定义如下：

循环展开公式

对于向量之间的圆周卷积操作 $\bullet$ 可以用傅里叶变换（DFT）来计算，即两个向量进行傅里叶变换后对应位置元素的乘积通过反傅里叶变换（IDFT）得到。

t-SVD分解：给定张量 $\mathit{A}\in \mathbb{R}^{\mathit{N}_{1}\times \mathit{N}_{2}\times \mathit{N}_{3}}$ ，它的t-SVD分解为：

$\mathit{A}=\mathit{U}\ast \mathit{S}\ast \mathit{V}^{T}$

其中U和V是正交张量，大小分别为 $N_{1}\times N_{1}\times N_{3}$ 和 $N_{2}\times N_{2}\times N_{3}$ 。S是f-对角张量，大小为 $N_{1}\times N_{2}\times N_{3}$ 。下图为t-SVD分解的算法流程图。其中fft为DFT的快速算法。

t-SVD算法流程图

主要步骤是在张量第三个维度进行FFT变换，然后对每个正面切片矩阵进行SVD分解就可以得到因子矩阵。t-SVD分解由于是对每个正面切片矩阵分别进行SVD分解，互相独立，因此可以用并行计算的方式来提高计算效率。但当数据维度过大时，消耗时间会显著增加。下图为t-SVD分解模型图。

t-SVD分解模型图

四、张量链分解

对于张量 $A\in \mathbb{R}^{I_{1}\times \cdots \times I_{N}}$ ，张量链分解定义为

$A\left ( i_{1},i_{2},\cdots ,i_{N} \right )=U_{1}\left ( :,i_{1},: \right )U_{2}\left ( :,i_{2},: \right )\cdots U_{N}\left ( :,i_{N},: \right )$

张量链的秩定义为 $rank_{TT}\left ( A \right )=\left ( S_{1},S_{2},\cdots S_{N+1} \right )$ ，其中 $S_{1}=S_{N+1}=1$ 。示意图如下

张量链模型图

五、张量环分解

对于张量 $A\in \mathbb{R}^{I_{1}\times \cdots \times I_{N}}$ ，张量环分解定义为

$A\left ( i_{1},i_{2},\cdots ,i_{N} \right )=tr\left ( U_{1}\left ( :,i_{1},: \right )U_{2}\left ( :,i_{2},: \right )\cdots U_{N}\left ( :,i_{N},: \right ) \right )$

张量环的秩定义为 $rank_{TR}\left ( A \right )=\left ( S_{1},S_{2},\cdots ,S_{N} \right )$ ，其中 $S_{N+1}=S_{1}$ 。示意图如下

张量环模型图

张量链是当 $S_{1}=1$ 时的特殊的张量环。张量链和张量环都属于简单的张量网络分解，并不是我所探讨问题的重点，因此后面的文章将不再涉及。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)