Mixed-integer programming methods for sparse optimization in signal processing

L’approximation parcimonieuse consiste à ajuster un modèle de données linéaire au sens des moindres carrés avec un faible nombre de composantes non nulles (la “norme” L0). En raison de sa complexité combinatoire, ce problème d’optimisation est souvent abordé par des méthodes sous-optimales. Il a cependant récemment été montré que sa résolution exacte était envisageable au moyen d’une reformulation en programme en nombres mixtes(MIP),couplée à un solveur MIP générique, mettant en œuvre des stratégies de type branch-and-bound. Cette thèse aborde le problème d’approximation parcimonieuse en norme L0 par la construction d’algorithmes branch-and-bound dédiés, exploitant les structures mathématiques du problème. D’une part, nous interprétons l’évaluation de chaque nœud comme l’optimisation d’un critère en norme L1, pour lequel nous proposons des méthodes dédiées. D’autre part, nous construisons une stratégie d’exploration efficace exploitant la parcimonie de la solution, privilégiant l’activation de variables non nulles dans le parcours de l’arbre de décision. La méthode proposée dépasse largement les performances du solveur CPLEX, réduisant le temps de calcul et permettant d’aborder des problèmes de plus grande taille. Dans un deuxième volet de la thèse, nous proposons et étudions des reformulations MIP du problème de démélange spectral sous contrainte de parcimonie en norme L0 et sous des contraintes plus complexes de parcimonie structurée, généralement abordées de manière relâchée dans la littérature.Nous montrons que, pour des problèmes de complexité limitée, la prise en compte de manière exacte de ces contraintes est possible et permet d’améliorer l’estimation par rapport aux approches existantes.Sparse approximation aims to fit a linear model in a least-squares sense, with a small number of non-zero components (the L0 “norm”). Due to its combinatorial nature, it is often addressed by suboptimal methods. It was recently shown, however, that exact resolution could be performed through a mixed integer program(MIP) reformulation solved by a generic solver, implementing branch-and-bound techniques. This thesis addresses the L0-norm sparse approximation problem with tailored branch-andbound resolution methods, exploiting the mathematical structures of the problem. First, we show that each node evaluation amounts to solving an L1-norm problem, for which we propose dedicated methods. Then, we build an efficient exploration strategy exploiting the sparsity of the solution, by activating first the non-zero variables in the tree search. The proposed method outperforms the CPLEX solver, reducing the computation time and making it possible to address larger problems. In a second part of the thesis, we propose and study the MIP reformulations of the spectral unmixing problem with L0-norm sparsity more advanced structured sparsity constraints, which are usually addressed through relaxations in the literature. We show that, for problems with limited complexity (highly sparse solutions, good signal-to-noise ratio), such constraints can be accounted for exactly and improve the estimation quality over standard approaches