Optimization algorithms for the tensor rank approximation problem : application to clustering in machine learning

Algorithmes d’optimisation pour le problème d’approximation des décompositions en rang tensoriel : application au clustering en apprentissage automatique Les tenseurs sont une généralisation d'ordre supérieur des matrices. Ils apparaissent dans une myriade d'applications. La décomposition de rang de tenseur decompose le tenseur en une somme minimale de tenseurs simples de rang 1. En pratique, la présence de bruit dans les entrées du tenseur fait que le calcul d'une décomposition de petit rang approchée est plus pertinente que de son calcul exacte. Ce problème est connu comme le problème d'approximation des décompositions en rang tensoriel. Dans cette thèse, nous étudions ce problème pour les tenseurs symétriques, c.à.d pour les tenseurs avec des entrées invariantes par les permutations d'indices. Nous considérons des tenseurs symétriques avec des valeurs complexes, parsuite en utilisant le lien entre les tenseurs et les polynômes homogènes, ainsi que des techniques d'optimisation complexe, nous proposons une approche d'optimisation riemannienne et nous développons un algorithme Newton riemannien et un algorithme Gauss--Newton riemannien pour résoudre ce problème. Nous abordons également le problème de diagonalisation simultanée de matrices, qui est étroitement lié au problème de décomposition tensorielle. Nous considérons ce problème sous deux angles: la certification et l'approximation. Pour la première partie, nous développons une suite de type Newton à convergence quadratique locale, et nous proposons un test de certification. Pour la deuxième partie, nous développons un algorithme de gradient conjugué riemannien qui calcule localement un faisceau de matrices simultanément diagonalisables approché. En combinant cet algorithme avec un problème linéaire des moindres carrés, nous introduisons un algorithme d'optimisation alterné qui calcule une approximation de la décomposition pour les tenseurs tridimensionnels, tels que le rang d'approximation est supérieur à la dimension de deux premiers modes. Enfin, en se basant sur les deux approches: tenseurs symétriques et diagonalisation simultanée de matrices, nous abordons le problème de de clustering en apprentissage automatique pour les modèles de mélanges de Gaussiènne sphériques. Nous utilisons ces méthodes pour implémenter la méthode des moments, afin de fournir un bon point initial pour l'algorithme de maximisation de vraissemblance.