Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Exact Sparse Approximation Problems via Mixed-Integer Programming: Formulations and Computational Performance

Sébastien Bourguignon 1 Jordan Ninin 2, 3 Hervé Carfantan 4 Marcel Mongeau 5
2 Lab-STICC_ENSTAB_CID_IHSEV
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
3 Pôle STIC_OSM
ENSTA Bretagne - École Nationale Supérieure de Techniques Avancées Bretagne
5 MAIA-OPTIM - ENAC Equipe MAIAA-OPTIM
MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
Abstract : Sparse approximation addresses the problem of approximately fitting a linear model with a solution having as few non-zero components as possible. While most sparse estimation algorithms rely on suboptimal formulations, this work studies the performance of exact optimization of problems through Mixed-Integer Programs (MIPs). Nine different sparse optimization problems are formulated based on or data misfit measures, and involving whether constrained or penalized formulations. For each problem, MIP reformulations allow exact optimization, with optimality proof, for moderate-size yet difficult sparse estimation problems. Algorithmic efficiency of all formulations is evaluated on sparse deconvolution problems. This study promotes error-constrained minimization of the norm as the most efficient choice when associated with and misfits, while the misfit is more efficiently optimized with sparsity-constrained and sparsity-penalized problems. Then, exact optimization is shown to outperform classical methods in terms of solution quality, both for over-and under-determined problems. Finally, numerical simulations emphasize the relevance of the different fitting possibilities as a function of the noise statistical distribution. Such exact approaches are shown to be an efficient alternative, in moderate dimension, to classical (suboptimal) sparse approximation algorithms with data misfit. They also provide an algorithmic solution to less common sparse optimization problems based on and misfits. For each formulation, simulated test problems are proposed where optima have been successfully computed. Data and optimal solutions are made available as potential benchmarks for evaluating other sparse approximation methods.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [45 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-01254856
Contributeur : Sébastien Bourguignon <>
Soumis le : mardi 12 janvier 2016 - 17:11:59
Dernière modification le : mardi 20 octobre 2020 - 10:32:07
Archivage à long terme le : : samedi 16 avril 2016 - 04:20:18

Fichier

MIP_sparse.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Sébastien Bourguignon, Jordan Ninin, Hervé Carfantan, Marcel Mongeau. Exact Sparse Approximation Problems via Mixed-Integer Programming: Formulations and Computational Performance. IEEE Transactions on Signal Processing, Institute of Electrical and Electronics Engineers, 2016, 64 (6), pp.1405-1419. ⟨10.1109/TSP.2015.2496367⟩. ⟨hal-01254856⟩

Partager

Métriques

Consultations de la notice

1381

Téléchargements de fichiers

1892