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

EasyChair Preprint no. 2569

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

@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 no. 2569},

  year = {EasyChair, 2020}}