# Quadratic Multilinear Discriminant Analysis for Tensorial Data Classification
## 3 Algorithm
While the above optimization problem is difficult to solve in general, it has an explicit solution in the case of vectors \(x_{1},\ldots,x_{m}\in\mathbb{R}^{n}\), and in this case we would recover the covariance matrix for each class. In this sense, the optimization problem we suggest can perhaps be also thought of as an extension of QDA to higher order data. Our method to estimate a solution is an alternating algorithm that iteratively keeps two of the three matrices fixed, and computes the third one. To deal with several tensors at once, we iteratively concatenate their flattenings along each of the modes. We can now describe the algorithm we use on each class to obtain a new set of coordinates. Let \(\mathcal{X}\) be the four-way tensor obtained by concatenating along the fourth mode all (centered) tensors \(\mathcal{X}_{1},\mathcal{X}_{2},\ldots,\mathcal{X}_{m}\) in class 1, and consider its matricizations \(\mathcal{X}_{(1)}\), \(\mathcal{X}_{(2)}\), and \(\mathcal{X}_{(3)}\) along the first, second, and third mode, respectively. Once a group \(G\) has been chosen (i.e., which group action to use in each mode), the problem to be solved is  
\[\operatorname*{arg\,min}_{(A,B,C)}\left(\sum_{i=1}^{m}|(A,B,C)\cdot\mathcal{X }_{i}|^{2}\right)=\operatorname*{arg\,min}_{(A,B,C)}\|(A,B,C,I)\cdot\mathcal{ X}\|^{2}.\]  
The challenge to solving the above problem is that the previous propositions do not readily extend to a method of minimizing in more than one mode simultaneously. On the other hand, we know how to minimize the norm in a given mode exactly. For this reason, we adopt an alternating algorithm, which keeps two of the matrices \(A\), \(B\) and \(C\) fixed at each step, and minimizes the norm with respect to the third one. If \(B\) and \(C\) are fixed and we call \(\mathcal{X}^{B,C}:=(I,B,C)\cdot\mathcal{X}\) the tensor obtained from \(\mathcal{X}\) after multiplying by \(B\) snd \(C\) in the second and third mode, respectively, the problem  
\[\operatorname*{arg\,min}_{A}\left(\sum_{i=1}^{m}|(A,B,C)\cdot\mathcal{X}_{i}| ^{2}\right)\]  
is equivalent to  
\[\operatorname*{arg\,min}_{A}|A\cdot\mathcal{X}_{(1)}^{B,C}|^{2},\]  
which can be solved using either Proposition 1 or Proposition 2 (depending on which group we chose to act on the first mode). Similarly,  
\[\operatorname*{arg\,min}_{B}\left(\sum_{i=1}^{m}|(A,B,C)\cdot\mathcal{X}_{i}| ^{2}\right),\]\[\operatorname*{arg\,min}_{C}\left(\sum_{i=1}^{m}\left\|(A,B,C)\cdot\mathcal{X}_{i} \right\|^{2}\right)\]  
are equivalent to  
\[\operatorname*{arg\,min}_{B}\left\|B\cdot\mathcal{X}_{(2)}^{A,C}\right\|^{2},\]  
\[\operatorname*{arg\,min}_{C}\left\|C\cdot\mathcal{X}_{(3)}^{A,B}\right\|^{2},\]  
where we defined \(\mathcal{X}^{A,C}:=(A,I,C)\cdot\mathcal{X}\) and \(\mathcal{X}^{A,B}:=(A,B,I)\cdot\mathcal{X}\). We keep iterating until each minimization reduces the norm beyond a given tolerance level, or a maximum chosen number of iterations is reached. As we will see in the experiments, this choice does not typically affect the outcome of the classification. Algorithm 1 describes this process. Figure 1 is a schematic graphical representation of Algorithm 1 in the case of matrix data (instead of third order tensors) for drawing ease. While we are not guaranteed the existence of a minimum, by Theorem 1 we know that if it exists, it is unique. Experimentally, it turns out that if we apply regularization at each iterative step, a minimum will exist in most cases. Figure 1: Graphical representation of Algorithm 1 in the case of matrix data. We can think of the group action via \((A,B,C)\) as a change of coordinates for centered tensors in a given class. Therefore to classify a new tensor \(\mathcal{Z}\) we apply a \(k\)-means algorithm, computing the distances \(d_{1}\) and \(d_{2}\) from the means of the two classes in the new coordinates. The process is described in Algorithm 2, which is our KNMDA algorithm. Figure 2 is a schematic graphical representation of Algorithm 2 in the case of matrix data (instead of third-order tensors) for drawing ease.