Paper notes（4）：Tensor Ring Decompoition

本文只是个人用于记录论文学习笔记，如有写错的地方还望各位大佬批评指正

1.文章提出的问题

$Tensor-Train\ Decomposition$Tensor−Train Decomposition 高度依赖于张量维度的排列，由于其在$latent\ cores$latent cores 上的多线性积遵循严格的顺序，所以很难找到最优的$TT$TT表示。

2.文章的主要创新点

本文针对$TTD$TTD的局限性，从三个方面进行了改进，提出了一种新的基础张量分解模型——$Tensor-Train\ Decomposition$Tensor−Train Decomposition，该模型将高维张量表示为一系列低维核张量(三维张量)上的环形多线性积。其图形化表示如下图所示:

3.Tensor Ring Model

$\mathcal{T}$T是一个$d$d维张量，大小为$n_1\times n_2\times \dotsm \times n_d$n1​×n2​×⋯×nd​，表示为$\mathcal{T} \in \mathbb{R}^{n_1\times n_2\times \dotsm \times n_d}$T∈Rn1​×n2​×⋯×nd​，$TRD$TRD将会把$\mathcal{T}$T分解为一系列张量$\mathcal{Z}_k \in \mathbb{R}^{r_k\times n_k\times r_{k+1}}$Zk​∈Rrk​×nk​×rk+1​(注意TRD分解所得的张量的大小和TTD分解所得张量大小的区别)，特别的$\mathcal{Z}_d \in \mathbb{R}^{r_d\times n_d\times r_1}$Zd​∈Rrd​×nd​×r1​，$\mathcal{T}$T的某一个元素可以表示为：
$\begin{aligned} \tag{1} \mathcal{T}(i_1,i_2,\dotsc,i_d) &=\text{Trace}\{Z_1(i_1)Z_2(i_2)\dotsc Z_d(i_d)\} \\ &=\text{Trace}\{\prod_{k=1}^d Z_k(i_k)\} \end{aligned}$T(i1​,i2​,…,id​)​=Trace{Z1​(i1​)Z2​(i2​)…Zd​(id​)}=Trace{k=1∏d​Zk​(ik​)}​(1)

其中$Z_k(i_k)$Zk​(ik​)表示张量$Z_k$Zk​的第$i_k$ik​个$lateral\ slice$lateral slice，其大小为$r_k\times r_{k+1}$rk​×rk+1​。$\mathcal{Z}_k$Zk​被称为$kth \text{-} core$kth-core；核张量的大小$r_k$rk​的集合表示为一个向量$r=\left[r_1, r_2, \dotsm，r_d\right]^T$r=[r1​,r2​,⋯，rd​]T，被称为$TR \text{-} ranks$TR-ranks。类似于$TTD$TTD公式(1)也可以表示为索引形式：
$\tag{2} \mathcal{T}(i_1,i_2,\dotsc,i_d) = \sum_{\alpha_1,\dotsm,\alpha_d=1}^{r_1,\dotsm,r_d} \prod_{k=1}^d Z_k(\alpha_k,i_k,\alpha_{k+1})$T(i1​,i2​,…,id​)=α1​,⋯,αd​=1∑r1​,⋯,rd​​k=1∏d​Zk​(αk​,ik​,αk+1​)(2)

其中$\alpha_{d+1} = \alpha_1, k \in \{1,\dotsm,d\},1 \leqslant \alpha_k \leqslant r_k, 1 \leqslant i_k \leqslant n_k$αd+1​=α1​,k∈{1,⋯,d},1⩽αk​⩽rk​,1⩽ik​⩽nk​。$TRD$TRD的张量表示形式如下：
$\tag{3} \mathcal{T} = \sum_{\alpha_1,\dotsm,\alpha_d=1}^{r_1,\dotsm,r_d} z_1(\alpha_1,\alpha_2) \circ \dotsm \circ z_d(\alpha_d,\alpha_1)$T=α1​,⋯,αd​=1∑r1​,⋯,rd​​z1​(α1​,α2​)∘⋯∘zd​(αd​,α1​)(3)

这里‘$\circ$∘’表示向量的外积运算，$z_k(\alpha_k,\alpha_{k+1}) \in \mathbb{R}^{n_k}$zk​(αk​,αk+1​)∈Rnk​表示$\mathcal{Z}_k$Zk​的第$(\alpha_k, \alpha_{k+1})$(αk​,αk+1​)个$mode \text{-} 2 \ fiber$mode-2 fiber（关于这一点可以参照三维张量的$mode \text{-} 2 \ fiber$mode-2 fiber示意图，理解起来很容易）。

4.TRD算法

张量$\mathcal{T}$T的$TRD$TRD分解表示为$\mathcal{T}=\mathfrak{R}(\mathcal{Z_1},\mathcal{Z_2},\dotsc,\mathcal{Z_d})$T=R(Z1​,Z2​,…,Zd​)，目标函数为：
$\tag{5} \min_{\mathcal{Z_1},\dotsc,\mathcal{Z_d}} = {\lVert \mathcal{T} - \mathfrak{R}(\mathcal{Z_1},\mathcal{Z_2},\dotsc,\mathcal{Z_d}) \rVert}_F \leqslant \epsilon_p {\lVert \mathcal{T} \rVert}_F$Z1​,…,Zd​min​=∥T−R(Z1​,Z2​,…,Zd​)∥F​⩽ϵp​∥T∥F​(5)

一些定义：

这篇文章给出了四种$TRD$TRD的算法，具体的算法伪代码请参看论文。

参考文献
1. Tensor Ring Dexomposition