Approche variationnelle de la fonction rang : relaxation convexe, sous-différentiation généralisée, régularisation-approximation de Moreau
Institution:
Toulouse 3Disciplines:
Directors:
Abstract EN:
In this dissertation, we consider the rank function from the variational point of view. The reason why we are interested in this function is that it appears as an objective (or constraint) function in various modern optimization problems, such as: low rank matrix completion, multivariate statistical data analysis, compressed sensing, etc. In some particular cases, the rank minimization problems can be solved by using the singular value decomposition of matrices or can be reduced to the solution of linear systems. But in general, the rank minimization problems is known to be « NP-hard ». We provide here several properties of the rank function from the variational point of view: additional proofs for its closed convex relaxation, the expressions of its generalized subdifferentials and the explicit expression of its Moreau regularization-approximation form. Then, in the last chapter, we revisit a notion whose definition resembles that of the rank, the cp-rank function.
Abstract FR:
Dans ce mémoire de these, nous étudions la fonction rang du point de vue variationnel. La raison pour laquelle nous nous intéressons à cette fonction est qu'elle apparaît comme une fonction objectif (ou comme fonction contrainte) dans divers problèmes d'optimisation moderne, par exemple: complétion de matrices, analyse de données statistiques, acquisition parcimonieuse de données, etc. Dans certains cas particuliers, les problèmes de minimisation de la fonction rang peuvent être résolus en utilisant la décomposition en valeurs singulières. Mais, en géneral, les problèmes de minimisation de la fonction rang sont « NP-difficiles ». Nous proposons ici quelques propriétés de la fonction rang du point de vue variationnel: des démonstrations supplémentaires pour son enveloppe convexe fermée (restreinte à des boules spectrales), les expressions des sous-différentiels généralisés et la régularisation-approximation au sens de Moreau. Puis, dans le dernier chapitre, nous revenons sur une notion dont la définition ressemble à celle de la fonction rang, la fonction cp-rang.