Optimisation non convexe pour la reconstruction de matrices de rang faible

Un « problème de reconstruction de matrice de rang faible » consiste à identifier, à partir d'un petit nombre d'informations, une matrice (c'est-à-dire un tableau de nombres), en sachant que celle-ci est « de rang faible » (ce qui, très informellement, revient à dire que ses lignes et colonnes présentent de grandes similarités entre elles). L'exemple le plus connu est le « problème Netflix » : les personnes qui utilisent Netflix attribuent des notes aux films qu'elles visionnent ; à partir de ces informations, peut-on deviner quelle note chaque utilisateur ou utilisatrice aurait donnée à chacun des films disponibles ? Dans ce cas, la matrice à identifier est l'ensemble des notes que chaque personne aurait attribuées à chaque film ; les informations sont les notes effectivement attribuées, c'est-à-dire une petite portion des nombres de la matrice.

Les matrices de rang faible apparaissant naturellement dans la plupart des domaines scientifiques, ces problèmes ont de nombreuses applications. Parmi les algorithmes conçus pour les résoudre, ceux dits « non convexes » consistent généralement à choisir une matrice de rang faible arbitraire puis à la modifier progressivement pour la rendre de plus en plus conforme aux informations accessibles, tout en veillant à ce qu'elle reste de rang faible. À première vue, ces algorithmes semblent naïfs : pourquoi ces modifications successives permettraient-elles d'identifier correctement la matrice inconnue ? Ne risque-t-on pas de s'égarer dans une suite infinie de petites modifications contradictoires, sans jamais parvenir à une matrice conforme simultanément à toutes les informations données ? Pourtant, en pratique, les algorithmes non convexes fonctionnent souvent bien et permettent de résoudre avec succès des problèmes de reconstruction a priori difficiles.

Cette constatation empirique est difficile à expliquer rigoureusement. Pour un problème et un algorithme non convexe donnés, on n'est en général pas capable de déterminer à l'avance si l'algorithme parviendra à résoudre le problème ; lorsqu'il y parvient, on ne sait pas expliquer pourquoi. Des avancées significatives ont néanmoins eu lieu depuis une dizaine d'années, avec le développement de méthodes générales permettant d'analyser, bien que sous des hypothèses contraignantes, certaines classes de problèmes et d'algorithmes. Le but de ce cours est de les présenter.