# Tensor-Based Algorithms for Image Classification
## 2 Prerequisites
### Tensor-Based Learning
#### 2.3.3 Supervised Learning with Tensor Networks  
It has been shown in [5; 6] that tensor-based optimization schemes can be adapted to supervised learning problems. A given input vector \(x\) is mapped into a higher-dimensional space using a feature map \(\boldsymbol{\
abla}\) before being classified by a decision function \(f\colon\mathbb{R}^{d}\to\mathbb{R}^{d^{\prime}}\) of the form  
\[f(x)=\boldsymbol{\Xi}^{\top}\boldsymbol{\
abla}(x), \tag{13}\]  
where \(\boldsymbol{\Xi}\) is a coefficient tensor in TT format. The \(i\)th entry of the vector \(f(x)\) then represents the likelihood that the image \(x\) belongs to the class with label \(i-1\). The transformation defined in [5; 6] reads as follows,  
\[\boldsymbol{\
abla}(x)=\begin{bmatrix}\cos(\alpha\,x_{1})\\ \sin(\alpha\,x_{1})\end{bmatrix}\otimes\begin{bmatrix}\cos(\alpha\,x_{2})\\ \sin(\alpha\,x_{2})\end{bmatrix}\otimes\cdots\otimes\begin{bmatrix}\cos( \alpha\,x_{d})\\ \sin(\alpha\,x_{d})\end{bmatrix}, \tag{14}\]where \(\alpha\) is a parameter. However, the originally proposed choice of \(\alpha=\frac{\pi}{2}\) is often not optimal. This will be discussed in more detail below. The function \(\boldsymbol{\
abla}\) assigns each pixel of the image a two-dimensional vector, inspired by the spin-vectors encountered in quantum mechanics [6]. It was illustrated in [14] how such a transformation can be implemented as a quantum feature map, where the information is encoded in the amplitudes of qubits. Embedding data into quantum Hilbert spaces might be interesting in cases where the quantum device evaluates kernels faster or where kernels cannot be simulated by classical computers anymore [14].  
Due to the tensor structure, \(\boldsymbol{\
abla}(x)\) is a tensor with \(2^{d}\) entries, which, for the original MNIST image size, amounts to \(n\approx 10^{236}\) basis functions. In [5; 6], the image size is first reduced to \(14\times 14\) pixels by averaging groups of four pixels, which then results in \"only\" \(n\approx 10^{59}\) basis functions. Thus, storing the full coefficient matrix is clearly infeasible since \(\Xi\in\mathbb{R}^{2\times\cdots\times 2\times d^{\prime}}\cong\mathbb{R}^{n \times d^{\prime}}\). Here, \(d^{\prime}\) appears as an additional tensor index since the decision function is computed for all \(d^{\prime}\) labels simultaneously.  
To learn the tensor \(\Xi\) from training data, a DMRG/ALS-related algorithm (cf. [4; 28]) that sweeps back and forth along the cores and iteratively minimizes the cost function  
\[\min_{\Xi}\sum_{j=1}^{m}\left\|y^{(j)}-\Xi^{\top}\boldsymbol{\
abla}(x^{(j)}) \right\|_{2}^{2} \tag{15}\]  
is devised. The suggested algorithm varies two neighboring cores at the same time, which allows for adapting the tensor ranks, and computes an update using a gradient descent step. The tensor ranks are reduced by truncated SVDs to control the computational costs. The truncation of the TT ranks can also be interpreted as a form of regularization. For more details, we refer to [5; 6].  
Different techniques to improve the original algorithm presented in [5] were proposed. In [29], the image data is preprocessed using a discrete cosine transformation and the ordering of the pixels is optimized in order to reduce the ranks. In [10], the DMRG-based sweeping method was replaced by a stochastic gradient descent approach, where the gradient is computed with the aid of automatic differentiation. Furthermore, it was shown that GPUs allow for an efficient solution of such problems.