# Tensor-Based Algorithms for Image Classification
## 2 Prerequisites
### Tensor-Based Learning
#### 2.3.1 Tensor Decompositions  
To mitigate the curse of dimensionality when working with tensors \(\mathbf{T}\in\mathbb{R}^{n_{1}\times\cdots\times n_{p}}\), where \(n_{\mu}\in\mathbb{N}\), we will exploit low-rank tensor approximations. The simplest approximation of a tensor of order \(p\) is a rank-one tensor, i.e., a tensor product of \(p\) vectors given by  
\[\mathbf{T}=T^{(1)}\otimes T^{(2)}\otimes\cdots\otimes T^{(p)}, \tag{7}\]where \(T^{(\mu)}\), \(\mu=1,\ldots,p\), are vectors in \(\mathbb{R}^{n_{\mu}}\). If a tensor is written as the sum of \(r\) rank-one tensors, i.e.,  
\[\mathbf{T}=\sum_{k=1}^{r}T^{(1)}_{;k}\otimes T^{(2)}_{;k}\otimes\cdots\otimes T ^{(p)}_{;k}, \tag{8}\]  
with \(T^{(\mu)}\in\mathbb{R}^{n_{\mu}\times r}\), this results in the so-called canonical format. In fact, any tensor can be expressed in this format, but we are particularly interested in low-rank representations of tensors in order to reduce the storage consumption as well as the computational costs. The same requirement applies to tensors expressed in the tensor train format (TT format), where a high-dimensional tensor is represented by a network of multiple low-dimensional tensors [21; 22]. A tensor \(\mathbf{T}\in\mathbb{R}^{n_{1}\times\cdots\times n_{p}}\) is said to be in the TT format if  
\[\mathbf{T}=\sum_{k_{0}=1}^{r_{0}}\cdots\sum_{k_{p}=1}^{r_{p}}\mathbf{T}^{(1)} _{k_{0},k_{1}}\otimes\cdots\otimes\mathbf{T}^{(p)}_{k_{p-1};k_{p}}. \tag{9}\]  
The tensors \(\mathbf{T}^{(\mu)}\in\mathbb{R}^{r_{\mu-1}\times n_{\mu}\times r_{\mu}}\) of order 3 are called TT cores. The numbers \(r_{\mu}\) are called _TT ranks_ and have a strong influence on the expressivity of a tensor train. It holds that \(r_{0}=r_{p}=1\) and \(r_{\mu}\geq 1\) for \(\mu=1,\ldots,p-1\). Figure 2a shows the graphical representation of a tensor train, which is also called Penrose notation, see [23]. The left- and right-unfoldings of a TT core \(\mathbf{T}^{(\mu)}\) are given by the matrices  
\[\mathcal{L}_{\mu}=\mathbf{T}^{(\mu)} \begin{vmatrix}r_{\mu}\\ r_{\mu-1},n_{\mu}\end{vmatrix} \in\mathbb{R}^{(r_{\mu-1}\cdot n_{\mu})\times r _{\mu}}\quad\text{and}\quad\mathcal{R}_{\mu}=\mathbf{T}^{(\mu)} \begin{vmatrix} n_{\mu}r_{\mu}\\ r_{\mu-1}\end{vmatrix} \in\mathbb{R}^{r_{\mu-1}\times(n_{\mu}\cdot r_{\mu})}, \tag{10}\]  
respectively. Here, the indices of two modes of \(\mathbf{T}^{(\mu)}\) are lumped into a single row or column index, whereas the remaining mode forms the other dimension of the unfolding matrix. We call the TT core \(\mathbf{T}^{(\mu)}\) left-orthonormal if its left-unfolding is orthonormal with respect to the rows, i.e., \(\mathcal{L}_{\mu}^{\top}\cdot\mathcal{L}_{\mu}=\mathrm{Id}\in\mathbb{R}^{r_{ \mu}\times r_{\mu}}\). Correspondingly, a core is called right-orthonormal if its right-unfolding is orthonormal with respect to the columns, i.e., \(\mathcal{R}_{\mu}\cdot\mathcal{R}_{\mu}^{\top}=\mathrm{Id}\in\mathbb{R}^{r_{ \mu-1}\times r_{\mu-1}}\). In Penrose notation, orthonormal components are depicted by half-filled circles, cf. Figure 2b, where a tensor train with left-orthonormal cores is shown. A given TT core can be left- or right-orthonormalized, respectively, by computing a singular value decomposition (SVD) of its unfolding. For instance, the components of an SVD of the form \(\mathcal{L}_{\mu}=U\cdot\Sigma\cdot V^{\top}\) can be interpreted as a left-orthonormalized version of \(\mathbf{T}^{(\mu)}\) coupled with the matrices \(\Sigma\) and \(V^{\top}\). When we talk about, e.g., left-orthonormalization of the cores of a tensor train, we mean the application of sequential SVDs from left to right (also called _HOSVD_, cf. [24]) where \(U\) builds the updated core, while the non-orthonormal part \(\Sigma\cdot V^{\top}\) is contracted with the subsequent TT core. As described in [13; 16; 25], left- and right-orthonormalization can be used to construct pseudoinverses of tensors.