Complétion de Matrices sur des Graphes

Le problème de trouver les valeurs manquantes d'une matrice à partir de quelques-unes de ses entrées, appelé complétion de matrice, a suscité beaucoup d'attention ces dernières années. Bien que le problème sous l'hypothèse standard de faible rang soit NP-difficile, Candès et Recht ont montré qu'il peut être exactement relaxé si le nombre d'entrées observées est suffisamment grand. Dans ce travail, nous introduisons un nouveau modèle de complétion de matrice qui utilise des informations de proximité sur les lignes et les colonnes en supposant qu'elles forment des communautés. Cette hypothèse est pertinente dans plusieurs problèmes du monde réel, tels que dans les systèmes de recommandation, où il existe des communautés de personnes partageant des préférences, tandis que les produits forment des clusters recevant des évaluations similaires.Notre objectif principal est donc de trouver une solution de faible rang structurée par les proximités des lignes et des colonnes codées par des graphes. Nous empruntons des idées issues de l'apprentissage sur variété pour contraindre notre solution à être lisse sur ces graphes, afin d'imposer implicitement les proximités entre lignes et colonnes. Notre modèle de récupération matricielle est formulé comme un problème d'optimisation convexe non différentiable, pour lequel un schéma itératif bien posé est fourni. Nous étudions et évaluons le modèle de complétion de matrice proposé sur des données synthétiques et réelles, montrant que le modèle de récupération structurée à faible rang proposé surpassent le modèle standard de complétion de matrice dans de nombreuses situations.