Switch back to the title and the abstract

Branch-and-Bound Algorithm for Sparse Approximation in Signal Processing and Statistics

EasyChair Preprint 2569

2 pages•Date: February 5, 2020

Ramzi Ben Mhenni, Sébastien Bourguignon and Jordan Ninin

Abstract

Sparse approximation aims to adjust a model in the least-squares sense and imposing a small number of non-zero components (the l_0 "norm"). This problem amounts to considering a mixed-integer program with binary constraints. We propose a Branch-and-Bound algorithm for the exploration of binary variables. We show that the evaluation of each node by continuous relaxation can be performed by solving l_1 norm minimization problems with box constraints, for which we propose a specific algorithm. The resulting method outperforms the generic CPLEX solver, especially when the size of the problem increases.

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

Links:

https://easychair.org/publications/preprint/GRcV

BibTeX entry

BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:

@booklet{EasyChair:2569,
  author    = {Ramzi Ben Mhenni and Sé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}}

Download PDF Open PDF in browser