Rでtensor train decomposition してみた

はじめに

Tensor train decomposition というテンソル分解の手法があります。あまりメジャーじゃないのかRで実装されている例をみないので作ってみました。

テンソルトレイン分解

TT.R

TT <- function(x,r)
{
D <- dim(x)
n<- length(D)
LIST <- rep(list(NA),n)
for (i in c(1:(n-1)))
{
if (i==1) {l0 <- 1} else {l0<- r[i-1]}
l1 <- r[i]
dim(x) <- c(D[i]*l0,prod(D[(i+1):n]))
SVD <- svd(x)
LIST[[i]] <- SVD$u[,1:l1]
dim(LIST[[i]]) <- c(l0,D[i],l1)
x<- t(SVD$u[,1:l1]) %*% x
}
LIST[[n]] <- t(x)
dim(LIST[[1]]) <- c(D[1],r[1])
return(LIST)
}

実行例

使い方は簡単です。テンソル$\mathcal{Z} \in \mathbb{R}^{N_1 \times N_2 \times \cdots \times N_m}$であるとします。
$r= (R_1, R_2, \cdots , R_{m-1})$を用意します。$R_i$はテンソル分解の次元をあたえる整数列です。
以下は$\mathcal{Z} \in \mathbb{R}^{3 \times 4 \times 5}, R_1=2,R_2=3$の場合の実行例です。

> set.seed(0)
> Z <- array(rnorm(3*4*5),c(3,4,5))
> dim(Z)
[1] 3 4 5
> r <- c(2,3)
> LIST <- TT(Z,r)
> LIST
[[1]]
           [,1]       [,2]
[1,] 0.33405782  0.4717883
[2,] 0.94144541 -0.1250656
[3,] 0.04567177 -0.8727969

[[2]]
, , 1

            [,1]        [,2]        [,3]       [,4]
[1,] -0.02676980  0.68746071  0.02735584 -0.6839789
[2,]  0.08867982 -0.08374744 -0.04396587  0.2032114

, , 2

            [,1]     [,2]       [,3]      [,4]
[1,] 0.005461026 0.161148  0.1228488 0.3503506
[2,] 0.094666990 0.485986 -0.2761150 0.7174820

, , 3

           [,1]       [,2]       [,3]       [,4]
[1,] 0.06102372 -0.3423556  0.6592200 -0.1576585
[2,] 0.41660602 -0.3899808 -0.2696078  0.1459710


[[3]]
           [,1]       [,2]       [,3]
[1,] -0.3594280  2.7946508 -1.4622505
[2,] -0.3689526 -0.3154154 -1.3315321
[3,] -1.7488794 -1.4190110 -0.6076388
[4,]  1.9922802 -2.1448302 -1.2577524
[5,]  3.2735897  0.8185284  0.1302124

> dim(LIST[[1]])
[1] 3 2
> dim(LIST[[2]])
[1] 2 4 3
> dim(LIST[[3]])
[1] 5 3

これだけです。テンソルトレイン分解は
$$
z_{i_1i_2,\cdots,i_m} \sim \sum_{r_1=1}^{R_1} \sum_{r_2=1}^{R_2} \cdots \sum_{r_{m-1}=1}^{R_{m-1}} G(i_1,r_1) G(r_1,i_2,r_2) \cdots G(r_{m-2},i_{m-1},r_{m-1}) G(i_m,r_{m-1})

$$
という分解をします。$G(i_1,r_1) \in \mathbb{R}^{N_1 \times R_1},G(i_m,r_{m-1}) \in \mathbb{R}^{N_m \times R_{m-1}}, G(r_{k-1}, i_k, r_k) \in \mathbb{R}^{R_{k-1} \times N_k \times R_k}$です。
この実行例ではLIST[[1]]に$G(i_1,r_1) \in \mathbb{R}^{N_1 \times R_1}$が、LIST[[2]]に$G(r_1,i_2,r_2) \in \mathbb{R}^{R_1 \times N_2 \times R_2}$が、LIST[[3]]に$G(i_3,r_2) \in \mathbb{R}^{N_3 \times R_2}$が、それぞれ入っています。

参考文献

SIAM J. Sci. Comput., 33(5), 2295–2317. (23 pages)
Tensor-Train Decomposition
I. V. Oseledets
https://doi.org/10.1137/090752286