Algorithme Branch-and-Bound Pour L’Approximation Parcimonieuse En Traitement Du Signal Et En Statistiques

EasyChair Preprint 2569

Abstract

L'approximation parcimonieuse consiste à ajuster un modèle au sens des moindres carrés avec un faible nombre de composantes non nulles (la "norme" l_0). Ce problème revient à considérer un programme en nombres mixtes avec des contraintes de binarité. Nous proposons un algorithme de type Branch-and-Bound pour l'exploration des variables binaires. Nous montrons que l'évaluation de chaque noeud par relaxation continue peut être réalisée en résolvant des problèmes en norme l_1 avec des contraintes de borne, pour lequel nous construisons un algorithme spécifique. La méthode résultante s'avère plus efficace que le solveur générique CPLEX, notamment lorsque la dimension du problème augmente.

Keyphrases: Algorithme Branch-and-Bound, Cardinalité, Optimisation en norme L0, Programmation en Nombres Mixtes

@booklet{EasyChair:2569,
  author    = {Ramzi Ben Mhenni and Sébastien Bourguignon and Jordan Ninin},
  title     = {Branch-and-Bound Algorithm for Sparse Approximation in Signal Processing and Statistics},
  howpublished = {EasyChair Preprint 2569},
  year      = {EasyChair, 2020}}