MDM classification as an optimization problem

The MDM algorithm [1] consists in finding the minimum distance between a trial and a class prototype before labeling the trial with the class that is the closest to the trial. It is a decision optimization problem that can be solved using Qiskit's QAOA, at conditions of 1) it is provided in the form of a convex model and, 2) it is quadratic, unconstrained and, contains only binary variables.

For instance, the MDM algorithm, based on Log-Euclidian metric has the following expression [2]:

$$\arg \min w^{T}Dw - 2 Vec(\log Y) D$$

• D - is the training data
• w - the vector we are trying to optimize
• Y - the new trial

with $\sum w_i = 1, w_i >= 0 \forall i$ and $D=[Vec(\log X_1)...Vec(\log X_N)]$, $Y$ being the trial and $X_i$ a class. These classes are built during training using the mean covariance matrices, and therefore this approach is compatible with the Quantum Optimized Riemannian mean.

Note that the equation above is a quadratic optimization problem. However, weights in the w vector are constrained continuous variables, thus complicating the use of the IntegerToBinary method (see Quantum Optimized Riemannian mean).

In addition, the equation must be solved for each new trial that needs to be classified. The complexity of determining the correct weight to minimize the equation varies as a function of the number of classes and the upper bound coefficient which is used for the IntegerToBinary method (the higher this coefficient, the higher the complexity). While potentially slower, this quantum-optimized version of the MDM algorithm could produce better results, especially in cases where classical computation fails.

References

[1] A. Barachant, S. Bonnet, M. Congedo, and C. Jutten, ‘Multiclass brain-computer interface classification by Riemannian geometry’, IEEE transactions on bio-medical engineering, vol. 59, no. 4, pp. 920–928, avril 2012, doi: 10.1109/TBME.2011.2172210.

[2] K. Zhao, A. Wiliem, S. Chen, and B. C. Lovell, ‘Convex Class Model on Symmetric Positive Definite Manifolds’, arXiv:1806.05343 [cs], May 2019.