# Tensor-Based Algorithms for Image Classification
## 3 Tensor-Based Classification Algorithms
### Basis Decomposition  
As above, let \(x\in\mathbb{R}^{d}\) be a vector and \(\psi_{n}\colon\mathbb{R}^{d}\to\mathbb{R}^{n_{\mu}}\), \(\mu=1,\ldots,p\), basis functions. We consider the rank-one tensors  
\[\boldsymbol{\
abla}(x)=\psi_{1}(x)\otimes\cdots\otimes\psi_{p}(x)= \begin{bmatrix} \psi_{1,1}(x)\\ \vdots\\ \psi_{1,n_{1}}(x)\end{bmatrix} \otimes\cdots\otimes \begin{bmatrix}\psi_{p,1}( x)\\ \vdots\\ \psi_{p,n_{p}}(x)\end{bmatrix} \in\mathbb{R}^{n_{1}\times n_{2}\times\cdots \times n_{p}}. \tag{16}\]  
For \(m\) different vectors stored in a data matrix \(X=[x^{(1)},\ldots,x^{(m)}]\in\mathbb{R}^{d\times m}\), we must construct transformed data tensors \(\boldsymbol{\
abla}_{X}\in\mathbb{R}^{n_{1}\times\cdots\times n_{p}\times m}\) with \((\boldsymbol{\
abla}_{X})_{:,\ldots,j}=\boldsymbol{\
abla}(x^{(j)})\). In [13; 16], this was achieved by multiplying (with the aid of the tensor product) the rank-one decompositions given in (16) for all vectors,  
Note that due to the tensor structure of \(\mathbf{\
abla}_{X}\), we obtain  
\[k\left(x^{(i)},x^{(j)}\right)=\prod_{\mu=1}^{p}\left\langle\psi_{\mu}\left(x^{(i) }\right),\,\psi_{\mu}\left(x^{(j)}\right)\right\rangle, \tag{25}\]  
i.e., a product of \(p\) local kernels. **Remark 1**. : _For the basis functions defined in (14), this can be simplified to_  
\[k(x,x^{\prime})=\prod_{i=1}^{d}\cos\left(\alpha(x_{i}-x_{i}^{\prime})\right), \tag{26}\]  
_which is a product of cosine kernels, cf. [5]._  
The product structure of the kernel allows us to compute the Gram matrix \(G\) as a Hadamard product (denoted by \(\odot\)) of \(p\) matrices, that is,  
\[G=\Theta_{1}\odot\Theta_{2}\odot\cdots\odot\Theta_{p}, \tag{27}\]  
where \(\Theta_{\mu}\in\mathbb{R}^{m\times m}\) is given by  
\[\Theta_{\mu}=\left[\psi_{\mu}\left(x^{(1)}\right),\ldots,\psi_{\mu}\left(x^{( m)}\right)\right]^{\top}\cdot\left[\psi_{\mu}\left(x^{(1)}\right),\ldots,\psi_{ \mu}\left(x^{(m)}\right)\right]. \tag{28}\]  
We now define \(Z:=Y\,G^{+}\in\mathbb{R}^{d^{\prime}\times m}\), which can be obtained by solving the system \(Z\,G=Y\) (in the least-squares sense if \(G\) is singular). The decision function \(f\), cf. (13), is then given by  
\[f(x)=\underbrace{Z\mathbf{\
abla}_{X}^{\top}}_{=:\mathbf{\Xi}^{\top}}\mathbf{\
abla}(x)=Z \begin{bmatrix}k(x_{1},x)\\ \vdots\\ k(x_{m},x)\end{bmatrix}  \tag{29}\]  
and again only requires kernel evaluations. As above, we can use a sequence of Hadamard products to compute \(\mathbf{\
abla}_{X}^{\top}\mathbf{\
abla}(x)\). The classification problem can thus be solved as summarized in Algorithm 1. ```
0: Training set \(X\) and label matrix \(Y\), test set \(\tilde{X}\), basis functions. 0: Label matrix \(\tilde{Y}\). ```  
```
1:Compute \(G\) using (27) and (28). 2:Solve \(Z\,G=Y\). 3:Define the decision function \(f\) using (29). 4:Apply \(f\) to every vector \(\tilde{x}\) in the test set, and store the resulting vectors \(\tilde{y}\) in the matrix \(\tilde{Y}\). 5:The index \(i\) of the largest entry of \(\tilde{y}\) determines the detected label, i.e., set \(\tilde{y}=e_{i}\). ```  
**Algorithm 1** Kernel-based MANDy for classification. We could also replace the pseudoinverse \(G^{+}\) by the regularized inverse \((G+\varepsilon\,\mathrm{Id})^{-1}\), where \(\varepsilon\) is the regularization parameter, which would lead to a slightly different system of linear equations. However, for the numerical experiments in Section 4, we do not use regularization. Algorithm 1 is equivalent to kernel ridge regression (see, e.g., [15]) with a tensor product kernel. This is not surprising, as we are solving simple least-squares problems. Note that the kernel does not necessarily have to be based on tensor products of basis functions for this method to work, we could also simply use, e.g., a Gaussian kernel, which for the MNIST data set leads to slightly lower but similar classification rates. Tensor-based kernels, however, have an exponentially large yet explicit feature space representation and additional structure that could be exploited to speed up computations.