# Tensor-Based Algorithms for Image Classification
## 3 Tensor-Based Classification Algorithms
### Alternating Ridge Regression  
In what follows, we will use the TT representation illustrated in Figure 3b for the transformed data tensor \(\boldsymbol{\Psi}_{X}\in\mathbb{R}^{n_{1}\times\cdots\times n_{p}\times m}\). Even though we do not consider a TT operator, the proposed approach is closely related to the DMRG method [4], also called alternating linear scheme (ALS) [28]. As in [5; 6], the idea here is to compute a low-rank TT approximation of the coefficient tensor \(\Xi\) by an alternating scheme. That is, a low-dimensional system of linear equations has to be solved for each TT core. Our approach is outlined in Algorithm 2. First, note that instead of solving the minimization problem (12), we can also find separate solutions of  
\[\min_{\Xi_{i}}\left\|Y_{i,\cdot}-\Xi_{i}^{\top}\boldsymbol{\Psi}_{X}\right\|_ {2} \tag{30}\]  
for each row of \(Y\). As these systems can be solved independently, Algorithm 2 can be easily parallelized. We then use a DMRG/ALS-inspired scheme to split the optimization problem (30) into \(p\) subproblems. The micromatrix \(M_{\mu}\) of such a subproblem can be built from three different parts, namely, \(\widehat{\boldsymbol{\Psi}}_{X,\mu}^{(\mu)}\), \(P_{\mu}\), and \(Q_{\mu}\). The latter are both collected in a left and right stack to avoid repetitive computations. Note that \(P_{\mu}\) is determined by contracting \(P_{\mu-1}\) with the \((\mu-1)\)th cores of \(\Xi_{i}\) and \(\widehat{\boldsymbol{\Psi}}_{X}\). Analogously, \(Q_{\mu}\) is build from \(Q_{\mu+1}\) and the \((\mu+1)\)th cores of \(\Xi_{i}\) and \(\widehat{\boldsymbol{\Psi}}_{X}\). During the first half sweep of Algorithm 2, we only have to compute the matrices \(P_{\mu}\), as the used matrices \(Q_{\mu}\) are not based on any updated cores. Afterwards, the matrices \(Q_{\mu}\) are (re-)computed during the second half. See [28] for further details and Figure 4 for a graphical illustration of the construction of the subproblems and the extraction of the optimized core. Note that it is not necessary to store the (sparse) core \(\widehat{\boldsymbol{\Psi}}_{X,\mu}^{(\mu)}\) in its full representation as a 4-dimensional array to construct the matrix \(M_{\mu}\). By using, e.g., NumPy's einsum the TT core can be replaced a (dense) matrix containing the corresponding function evaluations. ```
1:Training set \(X\) and label matrix \(Y\), test set \(\tilde{X}\), basis functions, initial guesses. 2:Label matrix \(\tilde{Y}\). ```
3:for\(i=1,\ldots,d^{\prime}\)do (parallelizable)
4: Define \(w=Y_{i,\cdot}=[Y_{i}^{(1)},\ldots,Y_{i}^{(m)}]\). 5: Define initial guess \(\Xi_{i}\) and right-orthonormalize. 6: Compute right stack \(Q_{p},\ldots,Q_{1}\). 7:for\(\mu=1,\ldots,p-1\)do (first half sweep)
8: Compute \(P_{\mu}\). 9: Construct micromatrix \(M_{\mu}\) from \(P_{\mu}\), \(\widehat{\mathbf{\Psi}}_{X,\mu}^{(\mu)},Q_{\mu}\). 10: Determine truncated SVD solution of \(\min_{v}\left\|w-vM_{\mu}\right\|_{2}\). 11: Apply QR decomposition to extract updated core. 12:for\(\mu=p,\ldots,1\)do (second half sweep)
13: Compute \(Q_{\mu}\). 14: Construct micromatrix \(M_{\mu}\) from \(P_{\mu}\), \(\widehat{\mathbf{\Psi}}_{X,\mu}^{(\mu)},Q_{\mu}\). 15: Determine truncated SVD solution of \(\min_{v}\left\|w-vM_{\mu}\right\|_{2}\). 16:if\(\mu>1\)then
17: Apply QR decomposition to extract updated core. 18:else
19: Set the updated core to a reshape of \(v\). 20: Repeat lines 5-17 to increase accuracy (if needed). 21: Define \(\Xi\) using (31) and set \(y=f(x)\) using (13). 22: The index of the largest entry of \(y\) determines the detected label, see Algorithm 1. Figure 4: Construction and solution of the subproblem for the \(\mu\)th core: (**a**) The 4-dimensional core of \(\widehat{\mathbf{\Psi}}_{X,\mu}\) (green circle) is contracted with the matrices \(P_{\mu}\) and \(Q_{\mu}\) constructed by joining the fixed cores of the coefficient tensor (orange circles) with the corresponding cores of the transformed data tensor. The matricization then defines the matrix \(M_{\mu}\).