Tensor Decomposition for Model Reduction in Neural Networks: A Review
Modern neural networks have revolutionized the fields of computer vision (CV)
and Natural Language Processing (NLP). They are widely used for solving complex
CV tasks and NLP tasks such as image classification, image generation, and
machine translation. Most state-of-the-art neural networks are
over-parameterized and require a high computational cost. One straightforward
solution is to replace the layers of the networks with their low-rank tensor
approximations using different tensor decomposition methods. This paper reviews
six tensor decomposition methods and illustrates their ability to compress
model parameters of convolutional neural networks (CNNs), recurrent neural
networks (RNNs) and Transformers. The accuracy of some compressed models can be
higher than the original versions. Evaluations indicate that tensor
decompositions can achieve significant reductions in model size, run-time and
energy consumption, and are well suited for implementing neural networks on
edge devices.
Xingyi Liu, Keshab K. Parhi
# Tensor Decomposition for Model Reduction in Neural Networks: A Review

###### Abstract

Modern neural networks have revolutionized the fields of computer vision (CV) and Natural Language Processing (NLP). They are widely used for solving complex CV tasks and NLP tasks such as image classification, image generation, and machine translation. Most state-of-the-art neural networks are over-parameterized and require a high computational cost. One straightforward solution is to replace the layers of the networks with their low-rank tensor approximations using different tensor decomposition methods. This paper reviews six tensor decomposition methods and illustrates their ability to compress model parameters of convolutional neural networks (CNNs), recurrent neural networks (RNNs) and Transformers. The accuracy of some compressed models can be higher than the original versions. Evaluations indicate that tensor decompositions can achieve significant reductions in model size, run-time and energy consumption, and are well suited for implementing neural networks on edge devices.

 Tensor decomposition, convolution neural network acceleration, recurrent neural network acceleration, Transformer acceleration, Canonical Polyadic decomposition, Tucker decomposition, Tensor Train decomposition, Tensor Ring decomposition, Block-Term decomposition, Hierarchical Tucker decomposition, model compression.

## I Introduction

Tensors are multidimensional arrays indexed by three or more indices. An \(N^{th}\)-order tensor is the tensor product of \(N\) vector spaces. Third-order tensors have three indices as shown in Fig. 1. In special cases, first-order tensors represent vectors, and second-order tensors represent matrices.

Convolutional neural networks (CNNs) have outperformed traditional techniques for image recognition tasks. In 2012, AlexNet [1] achieved about \(80\%\) top-5 accuracy on the ImageNet dataset [2]. Furthermore, subsequently VGG [3] and GoogleNet [4] achieved about \(90\%\) top-5 accuracy with the same dataset. On the ImageNet dataset, ResNet [5] with a depth of up to \(152\) layers achieved \(3.57\%\) top-5 error. Executing CNNs for computer vision tasks on mobile devices is gaining more and more attention. Common methods to reduce the size of CNNs include: sparsification [6, 7, 8, 9], quantization [1, 10], structural pruning [11, 12, 13, 14], and low-rank approximation [15, 16, 17, 18, 19, 20, 21, 22].

The use of low-rank approximations is inspired by [23] which showed that the neural network parameters are highly redundant. The authors in this paper could predict more than \(95\%\) of the weights of the network which indicates that the parameters of the CNNs are highly over-parametrized. Various low-rank tensor/matrix decompositions can be directly applied to the weights of convolutional and fully connected layers. In this paper, we review Canonical Polyadic decomposition (CPD) [15, 16, 17], Tucker decomposition [18, 19] and Tensor Train decomposition [20, 21] approaches to reduce model parameters of CNNs. The decomposed layers are replaced by a sequence of new layers with significantly fewer parameters.

Recurrent Neural Networks (RNNs) have shown promising success in sequence modeling tasks due to their ability in capturing temporal dependencies from input sequences [24, 25]. Their advanced variant, the Long Short-Term Memory (LSTM), introduces a number of gates and passes information with element-wise operations to address the gradient vanishing issue in vanilla RNNs [26]. These neural network architectures have shown promising performances in Natural Language Processing (NLP) [27], speech recognition [28] and computer vision (CV) [29]. The reader is referred to [30] for a review of various brain-inspired computing models.

Despite the success, RNNs and LSTMs suffer from a huge number of parameters which make the models notoriously difficult to train and susceptible to overfitting. In order to circumvent this problem, current approaches often involve exploring the low-rank structures of the weight matrices. Inspired by the implementation of tensor decomposition methods in CNNs [20], various tensor decomposition methods have been applied in RNNs and LSTMs, including Tensor Train Decomposition [31], Tensor Ring Decomposition [32], Block-Term Decomposition [33] and Hierarchical Tucker Decomposition [34]. These tensor-decomposed models can maintain high performance with orders-of-magnitude fewer parameters compared to the large-size vanilla RNNs/LSTMs.

Transformer is a deep learning model that is based on
the mechanism of self-attention by weighting the significance of each part of the input data differentially. It has led to breakthroughs in the fields of NLP and CV. Like RNNs, transformers are designed to process sequential input. However, transformers process the entire input all at once. For example, the transformers can process the whole natural language sentence at a time while the RNNs have to process word by word. The training parallelization allows transformers to be trained on larger datasets. This has led to the success of pre-trained systems such as BERT [35], GPT [36] and T5 [37]. However, the large model size of the Transformer based model may cause problems in training and inference under resource-limited environments. Tensorized embedding (TE) utilized the Tensor Train decomposition to compress the embedding layers of Transformers [38]. A novel self-attention model with Block-Term Decomposition was proposed to compress the attention layers of Transformers [39]. This method can not only largely compress the model size but also achieve performance improvement.

## II Tensor Decomposition Methods

A tensor decomposition is any scheme for compressing a tensor into a sequence of other, often simpler tensors. In this section, we review some tensor decomposition methods that are commonly used to compress deep learning models.

### _Truncated Singular Value Decomposition_

Given a matrix \(\mathbf{W}\in\mathbb{R}^{M\times N}\), the singular value decomposition (SVD) of the matrix is defined as:

\[\mathbf{W}=\mathbf{USV^{\intercal}},\]

where \(\mathbf{U}\in\mathbb{R}^{M\times M}\), \(\mathbf{S}\in\mathbb{R}^{M\times N}\) and \(\mathbf{V}\in\mathbb{R}^{N\times N}\). \(\mathbf{S}\) is the diagonal matrix with all the singular values on the diagonal. \(\mathbf{U}\) and \(\mathbf{V}\) are the corresponding orthogonal matrices. If the singular values of \(\mathbf{W}\) decay fast, then the weight matrix (\(\mathbf{W}\)) can be approximated by keeping only the \(K\) largest entries of \(\mathbf{S}\):

\[\widetilde{\mathbf{W}}=\widetilde{\mathbf{U}}\widetilde{\mathbf{S}}\widetilde{\mathbf{V}}^{ \intercal},\]

where \(\widetilde{\mathbf{U}}\in\mathbb{R}^{M\times K}\), \(\widetilde{\mathbf{S}}\in\mathbb{R}^{K\times K}\) and \(\widetilde{\mathbf{V}}\in\mathbb{R}^{K\times N}\). Then for any \(\mathbf{I}\in\mathbb{R}^{T\times M}\), the SVD approximation error satisfies:

\[||\mathbf{I}\widetilde{\mathbf{W}}-\mathbf{I}\mathbf{W}||_{F}\leq s_{K+1}||\mathbf{I}||_{F},\]

where \(||\cdot||_{F}\) denotes its Frobenius norm. Notice that the approximation error \(||\mathbf{I}\widetilde{\mathbf{W}}-\mathbf{I}\mathbf{W}||_{F}\) is controlled by \(s_{K+1}\), the \((K+1)^{th}\) largest singular value, or put another way, the decay along the diagonal of \(\mathbf{S}\). Considering the computation cost, \(\mathbf{I}\widetilde{\mathbf{W}}\) can be computed in \(\mathcal{O}(TMK+TK^{2}+TKN)\) which is much smaller than \(\mathcal{O}(TMN)\) for a sufficiently small \(K\).

### _Tensor Train Decomposition_

As defined in [40], the Tensor Train (TT) Decomposition of a tensor \(\mathcal{A}\in\mathbb{R}^{n_{1}\times n_{2}\times\cdots\times n_{d}}\) can be replaced by a set of matrices \(\mathbf{G}_{k}[j_{k}]\in\mathbb{R}^{r_{k-1}\times r_{k}}\) where \(j_{k}=1,2,\ldots,n_{k}\), \(k=1,2,\ldots,d\) and \(r_{0}=r_{d}=1\). Then each of the tensor elements can be computed as:

\[\mathcal{A}(j_{1},j_{2},\ldots,j_{d})=\mathbf{G}_{1}[j_{1}]\mathbf{G}_{2}[j_{2}]\ldots \mathbf{G}_{d}[j_{d}].\]

The sequence \(\{r_{k}\}_{k=1}^{d}\) is called TT-rank of the TT-representation of \(\mathcal{A}\). The collections of the matrices \(\{\{\mathbf{G}_{k}[j_{k}]\}_{j_{k}=1}^{n_{k}}\}_{k=1}^{d}\) are defined as TT-cores [40]. Notice that in TT-format, only \(\sum_{k=1}^{d}n_{k}r_{k-1}r_{k}\) parameters are required to represent a tensor \(\mathcal{A}\in\mathbb{R}^{n_{1}\times n_{2}\times\cdots\times n_{d}}\) which originally has \(\prod_{k=1}^{d}n_{k}\) elements. The trade-off between the model compression ratio and the reconstruction accuracy is controlled by the TT-ranks (\(\{r_{k}\}_{k=1}^{d}\)). The smaller the TT-ranks, the higher the model compression ratio TT-format can achieve. Another advantage of the TT-decomposition is that basic linear algebra operations can be applied to the TT-format tensors efficiently [40]. Fig. 2 from [41] shows that a third tensor \(\mathcal{A}\in\mathbb{R}^{3\times 4\times 5}\) can be represented by three TT-cores (\(\{\mathbf{G}_{d}\}_{d=1}^{3}\)) with \(32\) parameters in TT-format. Thus, the number of parameters needed to represent the original tensor is reduced from \(60\) to \(32\).

Tensor Train Decomposition utilizes two key ideas: recursively applying low-rank SVD and reshaping if the matrix is too thin. As illustrated in Fig. 3, a matrix of size \(8\times 10\) can be decomposed into five matrices \(G_{1}\) through \(G_{5}\) by recursively applying reshaping and low-rank SVD. Then these five matrices can be folded into five TT-cores of sizes \(1\times 2\times r_{1}\), \(r_{1}\times 2\times r_{2}\), \(r_{2}\times 2\times r_{3}\), \(r_{3}\times 2\times r_{4}\) and \(r_{4}\times 5\times 1\), respectively.

### _Canonical Polyadic Decomposition_

In 1927, the idea of expressing a tensor as the sum of a finite number of rank-one tensors was proposed by Hitchock [42, 43]. In 1970, the concept was generalized as CANDECOMP (canonical decomposition) by Carroll and Chang [44] and as PARAFAC (parallel factors) by Harshman [45].

The Canonical Polyadic (CP) decomposition factorizes a tensor into a sum of component rank-one tensors. For example, a third-order tensor \(\mathcal{X}\in\mathbb{R}^{I\times J\times K}\) can be approximated as:

\[\mathcal{X}\approx\sum_{r=1}^{R}\mathbf{a}_{r}\circ\mathbf{b}_{r}\circ\mathbf{c}_{r},\]

where \(\circ\) denotes the outer product of vectors. Parameter \(R\) is a positive integer and \(\mathbf{a}_{r}\in\mathbb{R}^{I}\), \(\mathbf{b}_{r}\in\mathbb{R}^{J}\) and \(\mathbf{c}_{r}\in\mathbb{R}^{K}\) for \(r=1,\ldots,R\). As shown in Fig. 4, each element of tensor \(\mathcal{X}\) can be computed as:

\[\mathbf{x}_{i,j,k}\approx\sum_{r=1}^{R}a_{ir}b_{jr}c_{kr},\]

where \(i=1,\ldots,I\), \(j=1,\ldots,J\), \(k=1,\ldots,K\). The factor matrices are defined as the combination of the vectors from the rank-one components: \(\mathbf{A}=[\mathbf{a}_{1}\quad\mathbf{a}_{2}\quad\ldots\quad\mathbf{a}_{R}]\), \(\mathbf{B}=[\mathbf{b}_{1}\quad\mathbf{b}_{2}\quad\ldots\quad\mathbf{b}_{R}]\) and \(\mathbf{C}=[\mathbf{c}_{1}\quad\mathbf{c}_{2}\quad\ldots\quad\mathbf{c}_{R}]\).
The rank of a tensor \(\mathcal{X}\) is defined as the smallest number of rank-one tensors that can generate the original tensor as their sum. Determining the rank of a specifically given tensor is NP-hard [46]. There is no straightforward algorithm to solve this problem. For a general third-order tensor \(\mathcal{X}\in\mathbb{R}^{I\times J\times K}\), the weak upper bound on its largest attainable rank is given by:

\[rank(\mathcal{X})\leq min\{IJ,IK,JK\}.\]

Any rank that occurs with positive probability is called a typical rank. Table I from [47] shows known typical ranks of specific third-order tensors over \(\mathbb{R}\).

Given the rank \(R\), there are many algorithms to compute the CP decomposition. Denton _et al._ computed the CP decomposition by the alternating least squares (ALS) method [16]. The

Fig. 4: CP decomposition of a third-order tensor.

Fig. 3: Tensor Train Decomposition of a matrix of size \(8\times 10\) by recursively applying reshaping and low-rank SVD. After decomposition and reshaping, the dimensions of the five TT-cores are \(1\times 2\times r_{1}\), \(r_{1}\times 2\times r_{2}\), \(r_{2}\times 2\times r_{3}\), \(r_{3}\times 2\times r_{4}\) and \(r_{4}\times 5\times 1\), respectively.

Fig. 2: Tensor Train Decomposition of a third-order tensor [41]. The original tensor has the dimensions \(3\times 4\times 5\). After decomposition, the dimensions of the three TT-cores are \(1\times 3\times 2\), \(2\times 4\times 2\) and \(2\times 5\times 1\), respectively. The number of parameters needed to represent the original tensor is reduced from \(60\) to \(32\).
ALS method was proposed in the original papers by Carroll and Chang [44] and Harshman [45].

```
procedure CP-ALS(\(\mathcal{X},R\))  initialize \(\mathbf{A}^{(n)}\in\mathbb{R}^{I_{n}\times R}\) for \(n=1,\ldots,N\) repeat for\(n=1,\ldots,N\)do \(\mathbf{V}\longleftarrow\mathbf{A}^{(1)\intercal}\mathbf{A}^{(1)}*\cdots*\mathbf{A}^{(n-1) \intercal}\mathbf{A}^{(n-1)}*\mathbf{A}^{(n+1)\intercal}\mathbf{A}^{(n+1)}*\cdots*\mathbf{A}^ {(N)\intercal}\mathbf{A}^{(N)}\); \(\mathbf{A}^{(n)}\longleftarrow\mathbf{X}^{(n)}(\mathbf{A}^{(N)}\odot\cdots\odot\mathbf{A}^ {(n+1)}\odot\mathbf{A}^{(n-1)}\odot\cdots\odot\mathbf{A}^{(1)})\mathbf{V}^{\uparrow}\);  normalize columns of \(\mathbf{A}^{(n)}\) (storing norms as \(\lambda\)); endfor until fit ceases to improve or maximum iterations exhausted return \(\lambda,\mathbf{A}^{(1)},\mathbf{A}^{(2)},\ldots,\mathbf{A}^{(N)}\) endprocedure
```

**Algorithm 1** ALS Algorithm [44, 45].

Given the rank \(R\), the ALS procedure for an \(N\)-th order tensor is shown in Algorithm 1 where \(*\) and \(\odot\) stand for the Hadamard and Khatri-Rao products of matrices, respectively. The factor matrices can be initialized randomly. The pseudo-inverse of a matrix \(\mathbf{V}\) of size \(R\times R\) must be computed at each iteration. The iterations stop when some stop conditions are satisfied, e.g., meeting the maximum iterations or little or no change in the factor matrices. The drawback of this algorithm is that subtracting the best rank-one tensor may increase tensor rank [54]. In [17], the authors used the non-linear least squares (NLS) method. Given the rank \(R\), NLS minimizes the \(L^{2}\)-norm of the approximation error by using Gauss-Newton optimization. NLS decomposition has significantly higher accuracy than the ALS with or without fine-tuning [17]. The Krylov-Levenberg-Marquardt algorithm was used for the CP decomposition with bounded sensitivity constraint in [55]. Furthermore, the authors in [56] propose a variant of the Error Preserving Correction (EPC) method that minimizes the sensitivity of the decomposition:

\[\min_{(\mathbf{A},\mathbf{B},\mathbf{C})}ss([[\mathbf{A},\mathbf{B},\mathbf{C}]])\] s,t \[\left|\mathcal{K}-[[\mathbf{A},\mathbf{B},\mathbf{C}]]\right|\right|_{F}^{2} \leq\delta^{2}\]

where \(ss([[\mathbf{A},\mathbf{B},\mathbf{C}]])\) represents the sensitivity of the CP decomposition and can be computed by [56]:

\[ss([[\mathbf{A},\mathbf{B},\mathbf{C}]])=K\cdot\mathrm{tr}\left\{(\mathbf{A}^{ \intercal}\mathbf{A})\vartriangle(\mathbf{B}^{\intercal}\mathbf{B})\right\}+\] \[I\cdot\mathrm{tr}\left\{(\mathbf{B}^{\intercal}\mathbf{B})\vartriangle( \mathbf{C}^{\intercal}\mathbf{C})\right\}+J\cdot\mathrm{tr}\left\{(\mathbf{A}^{\intercal} \mathbf{A})\vartriangle(\mathbf{C}^{\intercal}\mathbf{C})\right\},\]

where \(\vartriangle\) denotes the Hadamard element-wise product. The boundary \(\delta^{2}\) can be treated as the approximation error of the CP decomposition. See [56] for further details.

### _Tucker Decomposition_

Tucker decomposition was first proposed by Tucker [57, 58]. The Tucker decomposition can be treated as a form of higher-order principal component analysis (PCA). A third-order tensor \(\mathcal{X}\in\mathbb{R}^{I\times J\times K}\) can be decomposed into a core tensor multiplied by a matrix along each mode:

\[\mathcal{X} \approx\mathcal{G}\bullet_{1}\mathbf{A}\bullet_{2}\mathbf{B}\bullet_{3 }\mathbf{C}\] \[=\sum_{p=1}^{P}\sum_{q=1}^{Q}\sum_{r=1}^{R}g_{pqr}\mathbf{a}_{p}\circ \mathbf{b}_{q}\circ\mathbf{c}_{r}\] \[=[[\mathcal{G};\mathbf{A},\mathbf{B},\mathbf{C}]],\]

where \(\mathbf{A}\in\mathbb{R}^{I\times P}\), \(\mathbf{B}\in\mathbb{R}^{J\times Q}\) and \(\mathbf{C}\in\mathbb{R}^{K\times R}\) are the factor matrices and can be treated as the principal components in each mode. The tensor \(\mathcal{G}\in\mathbb{R}^{P\times Q\times R}\) is the core tensor. In the Tucker decomposition, each element of the original tensor \(\mathcal{X}\) can be represented by:

\[x_{i,j,k}\approx\sum_{p=1}^{P}\sum_{q=1}^{Q}\sum_{r=1}^{R}g_{pqr}a_{ip}b_{jq}c _{kr}, \tag{1}\]

for \(i=1,\ldots,I\), \(j=1,\ldots,J\) and \(k=1,\ldots,K\). The parameters \(P\), \(Q\), and \(R\) represent the number of components in the factor matrices \(\mathbf{A}\), \(\mathbf{B}\) and \(\mathbf{C}\), respectively. Fig. 5 shows the Tucker decomposition of a third-order tensor. In fact, CP decomposition can be viewed as a special case of the Tucker decomposition where the core tensor is superdiagonal and \(P\), \(Q\) and \(R\) are identical.

### _Tensor Ring Decomposition_

The limitation of setting the ranks hampers the flexibility and representation capability of the Tensor Train based models. When multiplying TT-cores, a strict order must be followed and the alignment of the tensor dimensions is critical in obtaining the optimized TT-cores. However, locating the best alignment is a hard problem [59].

Fig. 5: Tucker decomposition of a third-order tensor \(\mathcal{X}\).
The main modification of the tensor ring decomposition (TRD) is connecting the first and the last core tensors circularly to build a ring-like structure [32]. It can alleviate the limitation of the tensor train models as mentioned above. Formally, a \(d\)-dimensional target tensor \(\mathcal{X}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times I_{d}}\) can be decomposed as [32]:

\[\mathcal{X}\stackrel{{\rm TRD}}{{=}}\sum_{r_{0}=r_{d},r_{2}, \cdots,r_{d-1}}\mathcal{G}^{(1)}_{r_{0},I_{1},r_{1}}\mathcal{G}^{(2)}_{r_{1},I _{2},r_{2}}\cdots\mathcal{G}^{(d)}_{r_{d-1},I_{d},r_{d}}\]

The first and the last ranks are set to \(R\) (\(R>1\)). For any index \(k\) (\(k\in{1,2,\cdots,R}\)), the first order of the first core tensor \(\mathcal{G}^{(1)}_{r_{0}=k}\) and the last order of the last core tensor \(\mathcal{G}^{(d)}_{r_{d}=k}\) are matrices. The tensor ring structure can be regarded as a summation of \(R\) of tensor trains along each of the \(R\) slices of tensor cores. The product \(\mathcal{G}^{(1)}_{k,I_{1}}\mathcal{G}^{(2)}_{I_{2}}\cdots\mathcal{G}^{(d)}_{ I_{d},k}\) has the form of tensor train decomposition by fixing \(r_{0}=r_{d}=k\). Therefore, a tensor ring model is a linear combination of \(R\) different tensor train models. The tensor ring structure is illustrated in Fig. 6.

### _Block Term Decomposition_

Block Term decomposition combines CP decomposition and Tucker decomposition [33]. Given a \(d\)-dimensional target tensor \(\mathcal{X}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times I_{d}}\), it can be decomposed into \(N\) block terms as follows [33]:

\[\mathcal{X}\stackrel{{\rm BTD}}{{=}}\sum_{n=1}^{N}\mathcal{G}_{n }\bullet_{1}\mathcal{A}^{(1)}_{n}\bullet_{2}\mathcal{A}^{(2)}_{n}\bullet_{3} \cdots\bullet_{d}\mathcal{A}^{(d)}_{n}\]

where each term computes tensor-tensor product on \(k^{th}\) order (\(\bullet_{k}\)) between a core tensor \(\mathcal{G}_{n}\in\mathbb{R}^{R_{1}\times\cdots\times R_{d}}\) and \(d\) factor matrices \(\mathcal{A}^{(k)}_{n}\in\mathbb{R}^{I_{k}\times R_{h}}\) of \(\mathcal{G}_{n}\)'s \(k^{th}\) dimension, where \(n\in[1,N]\) and \(k\in[1,d]\)[60]. \(N\) is the CP-rank. \(R_{1},R_{2},\cdots,R_{d}\) are the Tucker-rank where \(d\) is the Core-order. Fig. 7 shows the block term decomposition for a \(3^{rd}\)-order tensor.

### _Hierarchical Tucker Decomposition_

Hierarchical Tucker decomposition has multiple hierarchical levels based on the order of the tensor. From top to bottom in a binary tree, a hierarchical tucker decomposed tensor can be recursively decomposed into intermediate tensors, referred as _frames_, as shown in Fig. 8. Each frame is a unique _node_ where each node is associated with a _dimension set_. Given a \(d\)-dimensional target tensor \(\mathcal{X}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times I_{d}}\), a binary tree with a root node associated with \(D=\{1,2,\cdots,d\}\) can be built where \(\mathcal{X}=\mathcal{U}_{D}\) is the root frame. For each non-leaf frame \(\mathcal{U}_{s}\in\mathbb{R}^{r_{s}\times I_{\mu_{s}}\times\cdots\times I_{ \nu_{s}}}\), \(s\subsetneq D\) is associated with the node corresponding to \(\mathcal{U}_{s}\) and \(s_{1},s_{2}\subsetneq s\) are associated with the left and right child nodes of the \(s\)-associated node where \(\mu_{s}=min(s)\) and \(\nu_{s}=max(s)\). A non-leaf frame \(\mathcal{U}_{s}\) can be recursively decomposed to a left child frame (\(\mathcal{U}_{s_{1}}\)), a right child frame (\(\mathcal{U}_{s_{2}}\)) and a transfer tensor ((\(\mathcal{G}\in\mathbb{R}^{r_{s}\times r_{s_{1}}\times r_{s_{2}}}\))) as follows [34]:

\[\mathcal{U}_{s}=\mathcal{G}_{s}\times_{1}^{2}\mathcal{U}_{s_{1}}\times_{1}^{2} \mathcal{U}_{s_{2}},\]

where \(\times_{1}^{2}\) denotes the tensor contraction that can be executed between two tensors with at least one matched dimension. For example, given two tensors \(\mathcal{A}\in\mathbb{R}^{n_{1}\times n_{2}\times l}\) and \(\mathcal{B}\in\mathbb{R}^{l\times m_{1}\times m_{2}}\) where the third dimension of \(\mathcal{A}\) matches the first dimension of \(\mathcal{B}\), a tensor of size \(n_{1}\times n_{2}\times m_{1}\times m_{2}\) can be computed by using the tensor contraction operation as \((\mathcal{A}\times_{1}^{3}\mathcal{B})_{i_{1},i_{2},j_{1},j_{2}}=\sum_{ \alpha=1}^{l}\mathcal{A}_{i_{1},i_{2},\alpha}\mathcal{B}_{\alpha,j_{1},j_{2}}\). The original \(I_{1}\times\cdots\times I_{d}\)-order tensor \(\mathcal{X}=\mathcal{U}_{D}\) can be recursively decomposed into a combination of the \(2^{nd}\)-order leaf frames and the \(3^{rd}\)-order transfer tensors by performing the hierarchical tucker decomposition from top to bottom of the binary tree. The parameter \(r_{s}\) is defined as _hierarchical rank_.

## III Tensorizing Convolutional Neural Networks

CNNs have two main parts: convolutional layers and fully connected layers. In general, convolutional layers in CNNs map a third-order input tensor \(\mathcal{X}\) of size \(S\times W\times H\) into a

Fig. 8: Hierarchical Tucker decomposition for a \(4^{th}\)-order tensor. It is a binary tree with root \(D=\{1,2,3,4\}\) where the dashed boxes represent the nodes. Node \(\{1\}\) is a leaf node whose parent and sibling are node \(\{1,2\}\) and node \(\{2\}\), respectively [34].

Fig. 6: Tensor Ring Decomposition in a ring form: the core tensors are multiplied one by one and form a ring [32].

Fig. 7: Block Term decomposition for a \(3^{rd}\)-order tensor. The tensor can be approximated by \(N\) Tucker decompositions where \(N\) is the CP-rank; \(R_{1},R_{2},R_{3}\) are the Tucker-rank; \(d\) is the Core-order [33].
third-order output tensor \(\mathcal{Y}\) of size \(T\times W^{\prime}\times H^{\prime}\) with a \(4^{th}\)-order kernel tensor \(\mathcal{K}\) of size \(T\times S\times D\times D\), where \(D\times D\) represents the filter size, \(S\) and \(T\) represent the number of input and output channels, respectively. The typical convolutional filter sizes are small, e.g., \(3\times 3\), \(7\times 7\), compared to the numbers of input (\(S\)) and output (\(T\)) channels. Each convolutional layer may have hundreds or thousands of filters which are suited for tensor decomposition methods. As shown in Fig. 9, the output tensor \(\mathcal{Y}\) can be computed as:

\[\mathcal{Y}_{t,w^{\prime},h^{\prime}}=\sum_{s=1}^{S}\sum_{j=1}^{D}\sum_{i=1}^ {D}\mathcal{K}_{t,s,j,i}\mathcal{X}_{s,w_{j},h_{i}},\]

where \(w_{j}=(w^{\prime}-1)q+j-p\) and \(h_{i}=(h^{\prime}-1)q+i-p\). The parameters \(p\) and \(q\) represent zero-padding size and stride, respectively.

Fully connected layers apply a linear transformation to an \(N\)-dimensional input vector \(\mathbf{x}\) and compute a \(M\)-dimensional output vector \(\mathbf{y}\):

\[\mathbf{y}=\mathbf{W}\mathbf{x}+\mathbf{b}. \tag{2}\]

where \(\mathbf{W}\) and \(\mathbf{b}\) represent the weight matrix and the bias vector, respectively. In this section, we show how these different tensor decomposition methods can be applied to CNNs.

### _Tensor Train Decomposition_

Tensor Train Decomposition can be applied to both the convolutional layers and the fully connected layers of CNNs. Let's first describe the implementation of TT-decomposition on the fully connected layers.

Now consider the TT-representation of the weight matrix \(\mathbf{W}\in\mathbb{R}^{M\times N}\) where \(M=\prod_{k=1}^{d}m_{k}\) and \(N=\prod_{k=1}^{d}n_{k}\). Define two bijection mappings \(\mu(t)=(\mu_{1}(t),\mu_{2}(t),\ldots,\mu_{d}(t))\) and \(\nu(t)=(\nu_{1}(t),\nu_{2}(t),\ldots,\nu_{d}(t))\) that map the matrix \(\mathbf{W}\) of size \(M\times N\) to a higher-order tensor \(\mathcal{W}\) of size \(n_{1}m_{1}\times n_{2}m_{2}\times\ldots n_{d}m_{d}\). The mapping \(\mu(\cdot)\) maps the row index \(\ell=1,2,\ldots,M\) of the matrix \(\mathbf{W}\) into a \(d\)-dimensional vector-indices whose \(k\)-th dimensions are of length \(m_{k}\). The mapping \(\nu(\cdot)\) maps the column index \(t=1,2,\ldots,N\) of the matrix \(\mathbf{W}\) into \(d\)-dimensional vector-indices whose \(k\)-th dimensions are of length \(n_{k}\). Thus the \(k\)-th dimension of the reshaped \(d\)-dimensional tensor \(\mathcal{W}\) is of length \(n_{k}m_{k}\) and is indexed by the tuple \((\mu_{k}(\cdot),\nu_{k}(\cdot))\). Then the tensor \(\mathcal{W}\) can be converted using TT-decomposition:

\[\mathbf{W}(\ell,t) =\mathcal{W}((\mu_{1}(\ell),\nu_{1}(t)),\ldots,(\mu_{d}(\ell), \nu_{d}(t)))\] \[=\mathbf{G}_{1}[(\mu_{1}(\ell),\nu_{1}(t))]\ldots\mathbf{G}_{d}[(\mu_{d}( \ell),\nu_{d}(t))].\]

The TT-format of the weight matrix transforms a \(d\)-dimensional tensor \(\mathcal{X}\) (formed from the input vector \(\mathbf{x}\)) to the \(d\)-dimensional tensor \(\mathcal{Y}\) (which can be used to compute output vector \(\mathbf{y}\)). As illustrated in Fig. 10 from [41], the linear transformation of a fully connected layer can be computed in the TT-format:

\[\mathcal{Y}(i_{1},\ldots,i_{d}) =\sum_{j_{1},\ldots,j_{d}}\mathbf{G}_{1}[i_{1},j_{1}]\ldots\mathbf{G}_{d}[ i_{d},j_{d}]\mathcal{X}(j_{1},\ldots,j_{d})\] \[\quad+\mathcal{B}(i_{1},\ldots,i_{d}).\]

where \(\mathcal{B}\) corresponds to the bias vector \(\mathbf{b}\) in Eq. (2). The ranks of the TT-format for the weight matrix depend on the choice of the bijection mappings \(\mu(t)\) and \(\nu(t)\). The computational complexity of the forward pass is \(\mathcal{O}(dr^{2}m\text{max}\{M,N\})\).

In machine learning, backpropagation is widely used to train feed-forward neural networks based on the stochastic gradient descent algorithm [24]. Backpropagation computes the gradient of the loss-function \(L\) with respect to all the parameters. Given the gradients with respect to the layer's output \(\frac{\partial L}{\partial\mathbf{y}}\), the backpropagation applied to the fully connected layers computes the gradients with respect to the input \(\mathbf{x}\), the weight matrix \(\mathbf{W}\) and bias vector \(\mathbf{b}\):

\[\frac{\partial L}{\partial\mathbf{x}}=\mathbf{W}^{\intercal}\frac{\partial L}{\partial \mathbf{y}},\frac{\partial L}{\partial\mathbf{W}}=\frac{\partial L}{\partial\mathbf{y}}\mathbf{ x}^{\intercal},\frac{\partial L}{\partial\mathbf{b}}=\frac{\partial L}{\partial\mathbf{y}}.\]

Notice that the gradient of the loss function with respect to the bias vector is the same as that with respect to the output. The gradient of the loss function with respect to the input vector \(\mathbf{x}\) can be computed using the same matrix-by-vector product as shown in Fig. 10 with the complexity of \(\mathcal{O}(dr^{2}m\text{max}\{M,N\})\). Instead of directly computing \(\frac{\partial L}{\partial\mathbf{W}}\) which requires \(\mathcal{O}(MN)\) memory, it's better to compute the gradient of the loss function \(L\) with respect to each TT-cores. The overall computation complexity of the backpropagation in the fully connected layer is \(\mathcal{O}(d^{2}r^{4}m\text{max}\{M,N\})\)[20]. See [20] for a detailed description of all the learning processes in the fully connected layers in TT-format.

We now review the implementation of TT-decomposition on convolutional layers. One straightforward way to represent the convolutional kernel \(\mathcal{K}\) in the TT-format is to apply the TT-decomposition directly to the tensor \(\mathcal{K}\). But in [21], the disadvantage of this method was mentioned. The kernel of a \(1\times 1\) convolution is a 2-dimensional array whose TT-format coincides with the matrix low-rank format. However, the matrix TT-format is more efficient than the matrix low-rank format [20].

The second approach of applying TT-decomposition to the convolutional layers is inspired by the theory that a convolutional layer can be formulated as a matrix-by-matrix multiplication [21, 61, 62]. As illustrated in Fig. 11, the two-dimensional convolution between a three-dimensional input tensor and a four-dimensional model is equivalent to the matrix-by-matrix multiplication [21].

Fig. 9: Original convolution layer with filter size of \(T\times S\times D\times D\).
In Fig. 11, \(H^{\prime}=H-D+1\) and \(W^{\prime}=W-D+1\), and the output tensor \(\mathcal{Y}\in\mathbb{R}^{T\times W^{\prime}\times H^{\prime}}\) is reshaped into a matrix \(\mathbf{Y}\in\mathbb{R}^{T\times W^{\prime}H^{\prime}}\) as follows:

\[\mathcal{Y}(t,y,x)=\mathbf{Y}(t,y+W^{\prime}(x-1)).\]

The matrix \(\mathbf{X}\) of size \(W^{\prime}H^{\prime}\times D^{2}S\) whose \(k\)-th row represents the \(S\times D\times D\) patch of the input tensor is generated by:

\[\mathcal{X}(s,y+j-1,x+i-1)=\mathbf{X}(x+W^{\prime}(y-1),j+D(i-1)+D^{2}(S-1)),\]

where \(y=1,\ldots,H^{\prime}\), \(x=1,\ldots,W^{\prime}\), \(i,j=1,\ldots,D\). Finally, the kernel tensor \(\mathcal{K}\) can be reshaped into a matrix \(\mathbf{K}\) of size \(D^{2}S\times T\):

\[\mathcal{K}(t,s,j,i)=\mathbf{K}(t,j+D(i-1)+D^{2}(S-1)).\]

After all these reshapings, the convolutional layers can be written as matrix-by-vector multiplication as shown in Fig. 11. Then the matrix TT-format can be directly applied to the matrix \(\mathbf{K}\): reshape it into a tensor \(\mathcal{K}\) and then convert it into the TT-format. Assume that the dimension of the matrix \(\mathbf{K}\) can be factorized as: \(S=\prod_{i=1}^{d}S_{i}\) and \(T=\prod_{i=1}^{d}T_{i}\). This assumption is always true since we can add some dummy channels to increase the values of \(S\) and \(T\). Then the (\(d+1\))-dimensional convolutional kernel whose \(k\)-th dimension has length \(D^{2}\) for \(k=0\) and \(S_{k}T_{k}\) for \(k=1,\ldots,d\) can be defined as:

\[\mathbf{K}(t^{\prime},x+D(y-1)+D^{2}(s^{\prime}-1))\] \[=\mathcal{K}((1,x+D(y-1)),(t_{1},s_{1}),\ldots,(t_{d},s_{d}))\] \[=\mathbf{G}_{0}[1,x+D(y-1)]\mathbf{G}_{1}[t_{1},s_{1}]\ldots\mathbf{G}_{d}[t_ {d},s_{d}],\]

where \(s^{\prime}=s_{1}+\sum_{i=2}^{d}(s_{i}-1)\prod_{j=1}^{i-1}S_{j}\) and \(t^{\prime}=t_{1}+\sum_{i=2}^{d}(t_{i}-1)\prod_{j=1}^{i-1}T_{j}\).

First, the TT-convolution layer reshapes the input tensor into a (\(d+2\))-dimensional tensor \(\mathcal{X}\in\mathbb{R}^{S_{1}\times\cdots\times S_{d}\times W\times H}\) and then transforms this tensor into the output tensor \(\mathcal{Y}\in\mathbb{R}^{T_{1}\times\cdots\times T_{d}\times(W-D+1)\times(H- D+1)}\) using the following equation:

\[\mathcal{Y}(t_{1},\ldots,t_{d},y,x)\] \[= \sum_{i=1}^{D}\sum_{j=1}^{D}\sum_{s_{1},\ldots,s_{d}}\mathcal{X} (s_{1},\ldots,s_{d},j+y-1,i+x-1)\times\] \[\mathbf{G}_{0}[1,y+D(x-1)]\mathbf{G}_{1}[t_{1},s_{1}]\ldots\mathbf{G}_{d}[t_ {d},s_{d}].\]

While training the network, the stochastic gradient is applied to each element of the TT-cores with momentum [21].

### _Canonical Polyadic Decomposition_

In CNNs, convolution layers map an input tensor of size \(S\ \times W\times H\) into an output tensor of size \(T\times W^{\prime}\times H^{\prime}\) using a kernel tensor of size \(T\times S\times D\times D\) where \(S\) and \(T\) represent different input and output channels, respectively. Now consider how to approximate the kernel tensor \(\mathcal{K}\) with

Fig. 11: Reducing convolution to a matrix-by-matrix multiplication [21].

Fig. 10: TT-format fully connected layer [41].
rank-\(R\) CP-decomposition. The number of the parameters needed to represent the kernel tensor of size \(T\times S\times D\times D\) after the decomposition is \(R(D^{2}+T+S)\) since the \(4\)-dimensional kernels are reshaped to \(3\)-dimensional kernels of size \(T\times S\times D^{2}\) as the filter size \(D\) is relatively small (e.g., \(3\times 3\) or \(5\times 5\)). The rank-\(R\) CP format of the reshaped kernel tensor can be represented as [15]:

\[\mathcal{K}_{t,s,j,i}=\sum_{r=1}^{R}\mathbf{U}_{r,s}^{(1)}\mathcal{U}_{r,j,i}^{(2) }\mathbf{U}_{t,r}^{(3)},\]

where \(\mathbf{U}_{r,s}^{(1)}\), \(\mathcal{U}_{r,j,i}^{(2)}\), \(\mathbf{U}_{t,r}^{(3)}\) are the three tensors of sizes \(R\times S\), \(R\times D\times D\) and \(T\times R\), respectively. Then the approximate transformation of the convolution from the input tensor \(\mathcal{X}\) to the output tensor \(\mathcal{Y}\) is given by:

\[\mathcal{Y}_{t,w^{\prime},h^{\prime}}=\sum_{r=1}^{R}\mathbf{U}_{t,r}^{(3)}(\sum_{ j=1}^{D}\sum_{i=1}^{D}\mathcal{U}_{r,j,i}^{(2)}(\sum_{s=1}^{S}\mathbf{U}_{r,s}^{(1)} \mathcal{X}_{s,w_{j},h_{i}})).\]

As shown in Fig. 12 from [15], this transformation is equivalent to a sequence of three separate small convolutional kernels in a row:

\[\mathcal{Z}_{r,w,h} =\sum_{s=1}^{S}\mathbf{U}_{r,s}^{(1)}\mathcal{X}_{s,w,h},\] \[\mathcal{Z^{\prime}}_{r,w^{\prime},h^{\prime}} =\sum_{j=1}^{D}\sum_{i=1}^{D}\mathcal{U}_{r,j,i}^{(2)}\mathcal{Z}_ {t,w_{j},h_{i}},\] \[\mathcal{Y}_{t,w^{\prime},h^{\prime}} =\sum_{r=1}^{R}\mathbf{U}_{t,r}^{(3)}\mathcal{Z^{\prime}}_{r,w^{\prime },h^{\prime}}.\]

where \(\mathcal{Z}_{r,w,h}\) and \(\mathcal{Z^{\prime}}_{r,w^{\prime},h^{\prime}}\) are intermediate feature tensors of sizes \(R\times W\times H\) and \(R\times W^{\prime}\times H^{\prime}\), respectively.

After this replacement, the entire network can be trained using a standard backpropagation process. Ranks play an important role in CP decomposition. Unfortunately, no polynomial time algorithm for determining the rank of a tensor exists [46, 48]. Therefore, most algorithms approximate the tensor with different ranks until a "good" rank is found. In [15], the authors applied rank-\(5\) CP decomposition first and then fine-tuned the whole network to balance the accuracy loss and the number of ranks. In [56], authors applied a heuristic binary search to find the smallest rank such that the accuracy drop after every single layer is acceptable.

### _Tucker Decomposition_

The \(4^{th}\)-order kernel tensor \(\mathcal{K}\) can be decomposed by the rank-(\(R_{1}\), \(R_{2}\), \(R_{3}\), \(R_{4}\)) Tucker decomposition as:

\[\mathcal{K}_{t,s,j,i}=\sum_{r=1}^{R_{1}}\sum_{r=1}^{R_{2}}\sum_{r =1}^{R_{3}}\sum_{r=1}^{R_{3}}\sum_{r=1}^{R_{4}}\mathcal{Q^{\prime}}_{r,r_{3},r,r_{1}}\mathbf{U}_{r,i}^{(1)}\mathbf{U}_{r,i}^{(2)}\mathbf{U}_{r,i}^{(3)}\mathbf{U}_{r,i}^{(4)},\]

where \(\mathcal{G^{\prime}}\) is the core tensor of size \(R_{4}\times R_{3}\times R_{2}\times R_{1}\) and \(\mathbf{U}^{(1)}\), \(\mathbf{U}^{(2)}\), \(\mathbf{U}^{(3)}\) and \(\mathbf{U}^{(4)}\) are the factor matrices of sizes sizes \(R_{1}\times D\), \(R_{2}\times D\), \(R_{3}\times S\) and \(R_{4}\times T\), respectively.

As mentioned before, the filter size \(D\) is relatively small compared to the number of input and output channels. Mode-1 and mode-2 which are associated with the filter sizes don't need to be decomposed. Under this condition, the kernel tensor can be decomposed by the Tucker-2 decomposition as follows:

\[\mathcal{K}_{t,s,j,i}=\sum_{r_{3}=1}^{R_{3}}\sum_{r_{4}=1}^{R_{4}}\mathcal{C}_ {r_{4},r_{3},j,i}\mathbf{U}_{r_{3},s}^{(3)}\mathbf{U}_{r_{4},t}^{(4)},\]

where \(\mathcal{C}\) represents the core tensor of size \(R_{4}\times R_{3}\times D\times D\). As shown in Fig. 13 from [19], this transformation is equivalent to a sequence of three separate small convolutional kernels:

\[\mathcal{Z}_{r_{3},w,h} =\sum_{s=1}^{S}\mathbf{U}_{r_{3},s}^{(3)}\mathcal{X}_{s,w,h},\] \[\mathcal{Z^{\prime}}_{r_{4},w^{\prime},h^{\prime}} =\sum_{r_{3}=1}^{R_{3}}\sum_{j=1}^{D}\sum_{i=1}^{D}\mathcal{C}_{r_ {4},r_{3},j,i}\mathcal{Z}_{r_{3},w_{j},h_{i}},\] \[\mathcal{Y}_{t,w^{\prime},h^{\prime}} =\sum_{r_{4}=1}^{R_{4}}\mathbf{U}_{t,r_{4}}^{(4)}\mathcal{Z^{\prime}} _{r_{4},w^{\prime},h^{\prime}},\]

where \(\mathcal{Z}\) and \(\mathcal{Z^{\prime}}\) are the intermediate tensors of sizes \(R_{3}\times W\times H\) and \(R_{4}\times W^{\prime}\times H^{\prime}\), respectively.

The rank-(\(R_{3},R_{4}\)) parameters are very important in the Tucker decomposition. They control the balance between the model compression ratio and accuracy loss. In [19], the authors applied global analytic solutions for variational Bayesian matrix factorization (VBMF) from [63] to determine the ranks of the Tucker decomposition. VBMF can be used to find noise variance, ranks and theoretical conditions for perfect rank recovery [63].

## IV Tensorizing Recurrent Neural Networks

In this section, implementations of applying different tensor decomposition methods to RNN models are described. This section demonstrates the core steps of four tensor-decomposed

Fig. 12: CP decomposed convolution layer in [15].

Fig. 13: Tucker-2 decomposed convolution layer in [19].
RNN models. 1) Transform \(W\) and \(x\) into tensor representations, \(\mathcal{W}\) and \(\mathcal{X}\); 2) Decompose \(\mathcal{W}\) into several low-rank tensors using different tensor decomposition methods; 3) the original product \(W\cdot x\) is approximated by the tensor computation between decomposed weight tensor \(\mathcal{W}\) and the input tensor \(\mathcal{X}\).

### _Tensorizing \(W\), \(x\) and \(y\)_

Considering \(W\) is a 2-D matrix, it should be reshaped since tensor decomposition methods are mainly applied to high-order tensors. The input vector \(x\in\mathbb{R}^{N}\), output vector \(y\in\mathbb{R}^{M}\) and the weight matrix \(W\in\mathbb{R}^{M\times N}\) should be tensorized into tensors \(\mathcal{X}\in\mathbb{R}^{n_{1}\times n_{2}\times\cdots\times n_{d}}\), \(\mathcal{Y}\in\mathbb{R}^{m_{1}\times m_{2}\times\cdots\times m_{d}}\) and \(\mathcal{W}\in\mathbb{R}^{m_{1}\times m_{2}\times\cdots\times n_{d}\times n_{ 2}\times\cdots\times n_{d}}\), respectively, where \(M=\prod_{i=1}^{d}m_{i}\) and \(N=\prod_{j=1}^{d}n_{j}\).

### _Decomposing \(W\)_

In general, the key idea of building tensor-decomposed RNN is to transform the input-to-hidden weight matrices in different tensor decomposition forms.

**Tensor Train Decomposition** Following the Tensor Train Decomposition method, \(\mathcal{W}\) can be decomposed into [31]:

\[TTD(\mathcal{W})=\mathcal{G}_{1}\mathcal{G}_{2}\cdots\mathcal{G}_{d}.\]

Now instead of storing the full tensor \(\mathcal{W}\) of size \(N\cdot M\), the set of low-rank core tensors \(\{\mathcal{G}\}_{k=1}^{d}\) of size \(\sum_{k=1}^{d}n_{k}\cdot m_{k}\cdot r_{k-1}\cdot r_{k}\) are stored.

**Tensor Ring Decomposition** Following the Tensor Ring Decomposition method, \(\mathcal{W}\) can be decomposed into [31]:

\[TRD(\mathcal{W})=\sum_{r_{0},\cdots,r_{2d-1}} \mathcal{G}_{r_{0},n_{1},r_{1}}^{(1)}\cdots\mathcal{G}_{r_{d-1},n _{d},r_{d}}^{(d)}.\] \[\mathcal{G}_{r_{d},m_{0},r_{d+1}}^{(d+1)}\cdots\mathcal{G}_{r_{2 d-1},m_{d},r_{0}}^{(2d)}\]

For a \(d\)-order input and \(d\)-order output, the weight tensor is decomposed into \(2d\) core tensors multiplied one by one where each corresponding to an input or an output dimension.

**Block Term Decomposition** Following the Block Term Decomposition method, \(\mathcal{W}\) can be decomposed into [33]:

\[BTD(\mathcal{W})=\sum_{n=1}^{N}\mathcal{G}_{n}\bullet_{1}\mathcal{A}_{n}^{(1)} \bullet_{2}\cdots\bullet_{d}\mathcal{A}_{d}^{(d)},\]

where \(\mathcal{G}\in\mathbb{R}^{R_{1}\times R_{2}\times\cdots\times R_{d}}\) is the core tensor, \(\mathcal{A}_{n}^{(d)}\in\mathbb{R}^{N_{d}\times M_{d}\times R_{d}}\) is the factor tensor, \(N\) denotes the CP-rank and \(d\) denotes the Core-order.

**Hierarchical Tucker Decomposition** Following the Hierarchical Tucker Decomposition method, \(\mathcal{W}\) can be decomposed into [34]:

\[HTD(\mathcal{W})= \sum_{k=1}^{r_{D}}\sum_{p=1}^{r_{D_{1}}}\sum_{q=1}^{r_{D_{2}}}( \mathcal{G}_{D})_{(k,p,q)}\] \[\cdot(\mathcal{U}_{D_{1}})_{(p,\phi_{D_{1}}(i,j))}(\mathcal{U}_{ D_{2}})_{(q,\phi_{D_{2}}(i,j))},\]

where the indices \(i=(i_{1},i_{2},\cdots,i_{d})\) and \(j=(j_{1},j_{2},\cdots,j_{d})\) are produced by the mapping function \(\phi_{s}(i,j)\) for frame \(\mathcal{U}_{s}\) with the given \(s\) and \(d\). Furthermore, \(\mathcal{U}_{D_{1}}\) and \(\mathcal{U}_{D_{2}}\) can be recursively calculated by:

\[(\mathcal{U}_{s})_{(k,\phi_{s}(i,j))}= \sum_{p=1}^{r_{s_{1}}}\sum_{q=1}^{r_{s_{2}}}(\mathcal{G}_{s})_{(k,p,q)}.\] \[(\mathcal{U}_{s_{1}})_{(p,\phi_{s_{1}}(i,j))}(\mathcal{U}_{s_{2}}) _{(q,\phi_{s_{1}}(i,j))},\]

where \(D=\{1,2,\cdots,d\}\), \(D_{1}=\{1,\cdots,\lfloor d/2\rfloor\}\) and \(D_{2}=\{\lceil d/2\rceil,\cdots,d\}\) are associated with the left and right child nodes of the root node.

### _Tensor Decomposition Layer_

After reshaping the weight matrix \(W\) and the input vector \(x\) into higher-order tensors and decomposing the weight tensor into tensor decomposed representations using the four different Tensor Decomposition methods as described above, the output tensor \(\mathcal{Y}\) can be computed by manipulating \(\mathcal{W}\) and \(\mathcal{X}\). The final output vector \(y\) can be obtained by reshaping the output tensor. The whole calculation from the input vector to the output vector can be denoted as the tensor decomposition layer (TDL):

\[y=TDL(W,x),\]

where TDL stands for one of Tensor Train Layer [31], Tensor Ring Layer [32], Block-Term Layer [33] and HT Layer [34] depending on the tensor decomposition method used.

Tensor-decomposed RNN models can be obtained by replacing the multiplication between the weight matrix \(W_{h}\) and input vector \(x\) with TDL. The hidden state \(h_{t}\) at time \(t\) can be computed as:

\[h_{t}=\sigma(TDL(W_{h},x_{t})+U_{h}h_{t-1}+b),\]

where \(\sigma(\cdot)\), \(W_{h}\) and \(U_{h}\) denote the activation function, the input-to-hidden layer weight matrix and the hidden-to-hidden layer matrix, respectively.

Replacing the multiplications between weight matrices and the input vector with TDL in the standard LSTM leads to:

\[f_{t} =\sigma(TDL(W_{f},x_{t})+U_{f}h_{t-1}+b_{f})\] \[i_{t} =\sigma(TDL(W_{i},x_{t})+U_{i}h_{t-1}+b_{i})\] \[o_{t} =\sigma(TDL(W_{o},x_{t})+U_{o}h_{t-1}+b_{o})\] \[g_{t} =tanh(TDL(W_{g},x_{t})+U_{g}h_{t-1}+b_{g})\] \[c_{t} =f_{t}\circ c_{t-1}+i_{t}\circ g_{t}\] \[h_{t} =o_{t}\circ tanh(c_{t}),\]

where \(\circ\), \(\sigma(\cdot)\) and \(tanh(\cdot)\) denote the Hadamard product (element-wise product), sigmoid function and the hyperbolic tangent function, respectively. The parameters \(f_{t}\), \(i_{t}\), \(o_{t}\), \(g_{t}\), \(c_{t}\) and \(h_{t}\) denote the forget gate's activation vector, input gate's activation vector, output gate's activation vector, cell input activation vector, cell state vector and hidden state vector, respectively. Note that \(W_{*}\), \(U_{*}\) and \(b_{*}\) (where \(*\) can be \(f\), \(i\), \(o\) or \(g\)) are weight matrices and bias vector parameters which need to be learned during training. Back Propagation Through
Time (BPTT) is used to compute the gradient of RNN [64]. Following the regular RNN backpropagation processing, the gradient \(\frac{dL}{Qy}\) is computed by the original BPTT algorithm, where \(y=Wx_{t}\). Using the corresponding tensorization operation same to \(y\), we can get the tensorized gradient \(\frac{dL}{Qy}\). All the tensorized RNN/LSTM models can be trained end-to-end directly. More details can be found in [31, 32, 33, 34].

## V Tensorizing Transformers

In 2017, a team at Google Brain introduced the Transformer [65] that gradually has become the preferred model for solving NLP problems, replacing RNN models such as LSTM [66]. In this section, we review two tensor decomposition methods applied on Transformers: tensorized embedding layers [38] and multi-linear attention [39] that compress the embedding layers and the multi-head attention in Transformer, respectively.

### _Multi-Linear Attention_

As shown in Fig. 14, the original Transformer model utilized an encoder-decoder architecture. The encoder is made up of encoding layers that process the input successively, while the decoder consists of decoding layers that perform the same as the output of the encoder. Each encoder layer's function is to create encodings that contain information about which parts of the input are mutually relevant. Those encodings are passed to the next layer of the encoder as inputs. The reverse is done by each decoder layer, which takes all encodings and generates an output sequence utilizing the contextual information. Both encoder and decoder layers make use of an attention mechanism.

The attention function is called "Scaled Dot-Product Attention". It computes an output as a weighted sum of the values, with each value's weight determined by the compatibility function of the query with the corresponding key. In practice, the attention function is computed on a set of queries simultaneously by packing queries, keys and values into matrices \(Q\), \(K\) and \(V\), respectively. Then the matrix of outputs can be computed as [65]:

\[Attention(Q,K,V)=softmax(\frac{QK^{T}}{\sqrt{d}})V,\]

where \(d\) is the number of columns of \(Q\) and \(K\). Instead of performing a single attention function, it is beneficial to linearly project the queries, keys and values \(h\) times using distinct linear projections. The attention function is then applied concurrently to each of these projected versions of queries, keys, and values. The final values of the attention function with different inputs are then concatenated and projected to generate the final values. Multi-head attention allows the model to learn from different representations at different positions. It can be expressed as follows [65]:

\[MultiHead(Q,K,V)=Concat(head_{1},\cdots,head_{h})W^{O}\] \[\text{where }head_{i}=Attention(QW_{i}^{Q},KW_{i}^{K},VW_{i}^{V}),\]

where matrices \(W_{i}^{Q}\), \(W_{i}^{K}\) and \(W_{i}^{V}\) have the same size of \(d_{model}\times d\) and \(W^{O}\in\mathbb{R}^{hd\times d_{model}}\).

Fig. 15(left) shows the schematic diagram of Single-block attention based on the Tucker decomposition. The query, key and value can be mapped into three-factor matrices (\(Q\), \(K\) and \(V\)) where each factor matrix is composed of three groups of orthogonal basis vectors. Then a new attention can be constructed by initializing a 3rd-order diagonal tensor \(\mathcal{G}\) as shown in Fig. 15(left) where \(R\), \(N\) and \(d\) represent the rank of the tensor, the length of the input sequence and the dimension of the matrix, respectively. The Tucker-decomposition inspired Single-block attention can be computed as [39]:

\[Atten_{TD}(\mathcal{G};Q,K,V)=\sum_{i=1}^{I}\sum_{j=1}^{J}\sum_{m=1}^{M} \mathcal{G}_{ijm}Q_{i}\circ K_{j}\circ V_{m},\]

where \(\mathcal{G}\) is the trainable core tensor and \(\circ\) represents the outer product. \(Q_{i}\), \(K_{j}\) and \(V_{k}\) represent the column vectors of matrices \(Q\), \(K\) and \(V\), respectively. Parameters \(i\), \(j\) and \(m\) are the indexes of the core tensor. In practice, the core tensor \(\mathcal{G}\) can be defined as [39]:

\[\mathcal{G}_{ijk}=\begin{cases}rand(0,1)&i=j=m\\ 0&otherwise\end{cases}\]

where \(rand(0,1)\) represent a random function. Then the Scaled Dot-Product attention can be computed by summing over the output of the Single-block attention function according to the second index as follows [39]:

\[Attention(Q,K,V)_{i,m}=\sum_{j=1}^{N}Atten_{TD}(\mathcal{G};Q,K,V)_{i,j,m},\]

where \(i\), \(j\) and \(m\) represent the indices of the output of the single-block attention.

Fig. 14: Model architecture of the Transformer [65].
In order to compress the multi-head function, multi-linear attention was proposed utilizing the idea of parameter sharing. As shown in Fig. 15(right), a set of linear projections map queries, keys and values to three matrices that can be composed of basis vectors. Then the multi-linear attention can be computed as follows [39]:

\[MultiLinear(\mathcal{G};Q,K,V) =SplitConcat(\frac{1}{h}*(T_{1}+\cdots+T_{h}))W^{O}\] \[\text{where }T_{j} =Atten_{TD}(\mathcal{G}_{j};QW^{q},KW^{k},VW^{v}),\]

where the core tensor \(\mathcal{G}_{j}\) is a diagonal tensor where \(j\in\{1,\cdots,h\}\). \(SplitConcat(\cdot)\) performs the concatenation following splitting. Matrices \(W^{q}\), \(W^{k}\) and \(W^{v}\) are the parameter matrices that are shared.

### _Tensorized Embedding Layers_

As shown in Fig. 14, the embedding layers convert input words into vectors in NLP tasks. However, large vocabulary results in enormous weight matrices, which prevents their use in situations with constrained resources. A parameter-efficient embedding layer, TT-embedding, was introduced [38]. The TT-embedding utilizes the Tensor Train decomposition by decomposing the huge embedding matrix into a sequence of much smaller 2-dimensional and 3-dimensional tensors. The method is the same as applying the Tensor Train decomposition to the fully connected layers of CNNs as described before.

Let \(X\in\mathbb{R}\) be the embedding matrix of size \(I\times J\) for a vocabulary of size \(I\) and embedding dimension \(J\). Given factorizations of its dimensions \(I=\prod_{k=1}^{N}I_{k}\) and \(J=\prod_{k=1}^{N}J_{k}\), the embedding matrix can be reshaped into a higher order tensor \(\mathcal{X}\in\mathbb{R}^{I_{1}J_{1}\times I_{2}J_{2}\times\cdots\times I_{N}J _{N}}\). Then the high order tensor can be decomposed into a sequence of smaller tensors \(\{\mathcal{G}_{k}\in\mathbb{R}^{R_{k-1}\times I_{k}\times J_{k}\times R_{k}} \}_{k=1}^{N}\). The sequence \(\{R_{k}\}_{k=1}^{N-1}\) represent the TT-ranks that directly affect the compression ratio.

## VI Results

### _Convolutional Neural networks_

In this section, the implementations and results of applying these tensor decomposition methods to some classical CNN models are described. They are categorized based on the tensor decomposition methods.

#### Vi-A1 Tensor Train Decomposition

In [21], Tensor Train decomposition was applied to the convolutional layers and fully connected layers as described before. The proposed method was tested on CIFAR-10 dataset from [67]. Two networks were built: one is dominated by the convolutional layers which occupy \(99.54\%\) parameters of the network and the other is dominated by the fully connected layers which occupy \(95.98\%\) parameters of the network. The first network consists of: conv with \(64\) output channels; batch normalization; ReLU; conv with \(64\) output channels; batch normalization; ReLU; max-pooling of size \(3\times 3\) with stride \(2\); conv with \(128\) output channels; batch normalization; ReLU; max-pooling of size \(3\times 3\) with stride \(2\); conv with \(128\) output channels; batch normalization; ReLU; conv with \(128\) output channels; avg-pooling of size \(4\times 4\); FC of size (\(128\times 10\)), where 'conv' and 'FC' stand for convolutional layer and fully connected layer, respectively. All convolutional filters were of size \(3\times 3\). Each convolutional layer excluding the first one was replaced by the TT-conv layer as mentioned before. The authors also compared the proposed Tensor Train decomposition method for the convolutional layer with the naive approach which directly applies the Tensor Train decomposition to the \(4^{th}\)-order convolutional kernel. As illustrated in TABLE II, the proposed approach can achieve similar accuracies as the naive baseline on the \(2\times\) compression level. The second network was adapted from the first one by replacing the average pooling with two fully connected layers of size \(8192\times 1536\) and \(1536\times 512\). Initially, the fully-connected part was the memory bottleneck. As shown in TABLE III, a \(21.01\times\) network compression with \(0.7\%\) accuracy drop can be achieved by only replacing the fully connected layers with TT-FC layers as described before.

Fig. 15: (left) Single-block attention using Tucker decomposition. (right) Multi-linear attention based on Block-Term tensor decomposition [39].
Then the bottleneck moves to the convolutional part. At this point, by additionally replacing the convolutional layers with the TT-conv layers, an \(82.87\times\) network compression with \(1.1\%\) accuracy drop can be achieved as shown in TABLE III. More details can be found in [21].

#### V-A2 CP Decomposition

In [17], CP decomposition was implemented in two steps: applying CP decomposition to the convolutional layer using the NLS algorithm and then fine-tuning the entire network using backpropagation. Two network architectures were tested: small character-classification CNN from [68] and AlexNet[1]. The character-classification CNN, called CharNet, has four convolutional layers. This CNN was used to classify images of size \(24\times 24\) into one of 36 classes (10 digits + 26 characters). Only the second and the third convolutional layers were compressed since they cost more than \(90\%\) of processing time. The second layer has \(48\) input channels and \(128\) output channels with filters of size \(9\times 9\). The third layer has \(48\) input channels and \(128\) output channels with filters of size \(8\times 8\). First, the second layer was compressed using CP decomposition with rank \(64\). Then all layers but the new ones were fine-tuned to reduce the accuracy drop. Finally, the third layer was approximated using CP decomposition with rank \(64\). Since the last approximation does not lead to a large accuracy drop, there is no need to fine-tune the network after that. The compressed network is \(8.5\) times faster than the original one while the classification accuracy only drops by \(1\%\) to \(90.2\%\). AlexNet is one of the common object recognition networks and it has eight layers consisting of five convolution layers and three fully connected layers. The second convolutional layer of AlexNet was compressed in [17] by using CP decomposition. The running time of the second layer can be accelerated by \(3.6\times\) using a rank of \(200\) at the expense of \(0.5\%\) accuracy degradation or by \(4.5\times\) with a rank of \(140\) at the expense of \(\approx 1\%\) accuracy degradation. Another fact mentioned in [17] is that greedy CP decompositions like ALS work worse than NLS for CNN model compression.

Tensor Power Method (TPM) [69] was used to apply CP decomposition to the convolutional kernels in [15]. Compared to ALS, TPM can achieve the same variance with less rank since the rank-\(1\) tensors found in the early steps of TPM represents most of the variances in the original tensor. TPM compressed the convolutional kernels by adding rank-\(1\) tensors until a predefined number of rank-\(1\) tensors is found. First, TPM finds a rank-\(1\) tensor \(\mathcal{K}_{1}\) by minimizing \(||\mathcal{K}-\mathcal{K}_{1}||_{2}\). The next iteration approximates the residual tensor \(\mathcal{K}_{residual}=\mathcal{K}-\mathcal{K}_{1}\) by minimizing \(||\mathcal{K}_{residual}-\mathcal{K}_{2}||_{2}\). This continues until \(\mathcal{K}_{R}\) is found. More details can be found in [69]. It is the first time that CP-based decomposition is applied to the whole convolutional layer in [15]. AlexNet was used here. The authors overcome the instability of CP decomposition by fine-tuning after each layer's decomposition. The fully connected layers were decomposed using SVD as described before. Fig. 16 from [15] shows that decomposition and fine-tuning are performed iteratively from Conv1 to FC8. Black solid arrows represent the connection between each layer. Red dotted lines represent the decomposition processes. Black dotted lines show that the weights do not change from the previous iteration. Purple block arrows represent fine-tuning by backpropagation to the whole network. The rank of each layer was set to be proportional to its sensitivity which is defined as _loss/total_loss_. This method achieved \(6.98\times\) parameter reduction and \(3.53\times\) running time reduction with the expense of \(1.42\%\) accuracy loss.

#### V-A3 Tucker Decomposition

In [19], one-shot Tucker Decomposition on the whole network consists of three steps: rank selection using VBMF, Tucker decomposition on each layer's kernel tensor and one-shot fine-tuning the whole network with standard back-propagation. Fig. 17 from [19] shows the whole scheme. The accuracy significantly dropped after step two but recovered quickly in one epoch. Four representative CNNs, AlexNet, VGG-S, GoogLeNet and VGG-16 were compressed using Tucker decomposition in [19]. For GoogLeNet, only the 3 \(\times\) 3 convolution kernel was compressed in the case of inception module. For VGG-16, only the convolutional layers were compressed. This method achieved \(5.46\times\) / \(2.67\times\) (AlexNet), \(7.40\times\) / \(4.80\times\) (VGG-S), \(1.28\times\) / \(2.06\times\) (GoogLeNet) and \(1.09\times\) / \(4.93\times\) (VGG-16) reductions in total weights and FLOPs, respectively.

### _Recurrent Neural Networks_

In this section, the results of applying different tensor decomposition methods to RNN models are described.

To better understand the impact of different tensor decomposition methods on RNNs, the time complexity and space complexity of different RNN models are summarized in Table IV. Notice that HT-RNN has the lowest space complexity and TT-RNN has the lowest time complexity.

The UCF11 YouTube Action dataset [70] contains \(1600\) video clips of a resolution \(320\times 240\), falling into \(11\) action
categories (e.g., basketball, biking, diving, etc.). Each category contains \(25\) video groups, within each contains more than \(4\) clips. Table V summarizes the performance of different tensor-decomposed LSTM models on UCF11 dataset. Notice that HT-LSTM requires at least \(1.38\times\) fewer parameters with at least \(0.3\%\) increase in accuracy compared to the other tensor-decomposed LSTM models.

### _Transformers_

In this section, the results of applying different tensor decomposition methods to Transformers are described.

#### Iv-C1 Multi-Linear Attention

The proposed attention method was tested on three language modeling tasks (PTB, WikiText-103 and One-billion) and a neural machine translation task (WMT-2016 English-German) [39].

Language modeling is the task of predicting the next word or character in a document. It can be used to generate text or further fine-tuned to solve different NLP tasks [36]. Three datasets were chosen: one of small size (PTB), one of medium size (WikiText-103) and one of large size (One-billion). PTB contains 929,900 training tokens, 73,900 validation words, and 82,900 test words [71]. WikiText-103 has 267,735 distinct

Fig. 16: CP-TPM method in AlexNet [15]. The black solid arrow represents the connection between layers. The red dotted line stands for the decomposition process and the black dotted line means that the weights are taken from the previous iteration. The purple block arrow stands for fine-tuning by backpropagation to all the layers. First, Conv is decomposed into \(2\) layers while the others remain the same. Then, fine-tuning is performed on the whole network. Afterward, Conv2 is decomposed into \(3\) layers and then fine-tuning is performed on the whole network followed. The process repeats until all the layers are decomposed and fine-tuned.

Fig. 17: One-shot whole network compression based on Tucker decomposition [19]. Tucker-2 decomposition is applied from the second convolutional layer to the first fully connected layers while Tucker-1 decomposition is applied to the other layers.
tokens. The dataset is a long-term dependency word-level language modeling benchmark. It contains 103 million training tokens from 28 thousand articles, with an average length of 3.6 thousand tokens per article. The One-Billion Word benchmark is a large dataset with 829,250,940 tokens over a vocabulary of 793,471 words. Models were evaluated based on the average per-word log-probability, Perplexity (PPL). The lower the PPL, the more accurate the model. The standard multi-head attention layers in Transformer were replaced with Multi-linear attention. A comparison of different model configurations on different datasets is shown in Table VI and Table VII. Notice that the tensorized transformer with Multi-linear attention achieves lower PPL with much fewer parameters than other models in the three datasets.

Neural Machine Translation involves translating text or speech from one language to another. The baseline is a vanilla Transformer trained on WMT 2016 English-German dataset [83]. For comparison, each of the attention layers was replaced with Multi-linear attention in the Encoder of the Transformer. The results are summarized in Table VIII. Notice that tensorized transformers with Multi-linear attention achieve better performance with fewer parameters than the vanilla Transformer.

#### Vi-B2 Tensorized Embedding Layers

The proposed TT-embedding layer was tested on two language modeling tasks (PTB and WikiText-103) and a machine translation task (WMT 2014 English-German). As shown in Table VII, Transformer-XL+TT stands for the transformers with TT-embedding layers. Compared to the Transformer with Multi-linear attention, Transformer-XL+TT can not achieve that high compression ratio. For the machine translation task, the baseline is a Transformer-big model on WMT 2014 English-German dataset [65]. This dataset has around 4.5 million sentence pairs. The results are summarized in Table IX. Notice that the embedding layers can be compressed significantly at the cost of a small drop in the BLEU scores.

## VII Conclusion

This paper has summarized different tensor decomposition methods that are used to compress model parameters of CNNs, RNNs and Transformers. In particular, three decomposition methods for CNNs, four decomposition methods for RNNs and two decomposition methods for Transformers have been reviewed. Finding the best rank for the low-rank approximation remains a challenge and has to be found by trial and error. The model compression ratio is dependent on the rank approximation and the performance degradation that can be tolerated. For RNNs, the model compression ratio is much higher than those of CNNs. Additionally, the accuracy of the compressed RNN model can be better than the original model. All these models are trained end-to-end using backpropagation instead of being obtained by applying tensor decomposition methods to the pre-trained standard models. It is possible for them to achieve higher accuracy than the standard models with fewer parameters.

Future work needs to be directed toward comparing the performance of various decomposition methods using common datasets. Hardware-aware Tucker Decomposition was proposed to efficiently generate highly accurate and compact CNN models on GPUs [85]. Algorithm and Hardware Co-Design of high-performance energy-efficient LSTM networks was introduced based on Hierarchical Tucker Tensor Decomposition [86]. Future research also needs to be directed toward the evaluation of the hardware performance of these decomposition methods.
