Solutions garanties de solutions de rang minimum des équations matricielles linéaires via la minimisation de la norme nucléaire

Le problème de minimisation de rang affine consiste à trouver une matrice de rang minimum qui satisfait un système donné de contraintes d'égalité linéaires. De tels problèmes sont apparus dans la littérature d'un ensemble divers de domaines, y compris l'identification et le contrôle des systèmes, l'embedding euclidien, et le filtrage collaboratif. Bien que des instances spécifiques puissent souvent être résolues avec des algorithmes spécialisés, le problème général de minimisation de rang affine est NP-difficile car il contient la minimisation de la cardinalité vectorielle comme cas spécial. Dans cet article, nous montrons que si une certaine propriété d'isométrie restreinte est satisfaite pour la transformation linéaire définissant les contraintes, la solution de rang minimum peut être récupérée en résolvant un problème d'optimisation convexe, à savoir, la minimisation de la norme nucléaire sur l'espace affine donné. Nous présentons plusieurs ensembles aléatoires d'équations où la propriété d'isométrie restreinte est satisfaite avec une probabilité écrasante, à condition que la codimension du sous-espace soit suffisamment grande. Les techniques utilisées dans notre analyse ont de forts parallèles dans le cadre du traitement compressé. Nous discutons de la manière dont la minimisation de rang affine généralise ce concept préexistant et esquissons un dictionnaire reliant les concepts de minimisation de cardinalité à ceux de minimisation de rang. Nous discutons également de plusieurs approches algorithmiques pour minimiser la norme nucléaire et illustrons nos résultats avec des exemples numériques.