Sparse Branch and Bound for Exact Optimization of L0-Norm Penalized Least Squares

Ramzi Ben Mhenni (1) , Sébastien Bourguignon (1) , Marcel Mongeau (2) , Jordan Ninin (3) , Hervé Carfantan (4)

1 LS2N - Laboratoire des Sciences du Numérique de Nantes
2 ENAC - Ecole Nationale de l'Aviation Civile
3 Lab-STICC_ENSTAB_CID_PRASYS
4 IRAP - Institut de recherche en astrophysique et planétologie

We propose a global optimization approach to solve ℓ 0 -norm penalized least-squares problems, using a dedicated branch-and-bound methodology. A specific tree search strategy is built, with branching rules inspired from greedy exploration techniques. We show that the subproblem involved at each node can be evaluated via ℓ 1 -norm-based optimization problems with box constraints, for which an active-set algorithm is built. Our method is able to solve exactly moderate-size, yet difficult, sparse approximation problems, without resorting to mixed-integer programming (MIP) optimization. In particular, it outperforms the generic MIP solver CPLEX.

Mots clés: Sparse approximation; Inverse problems; Optimization; Branch & Bound; Active set algorithm

Domaines: Traitement du signal et de l'image [eess.SP]; Recherche opérationnelle [math.OC]

Ramzi Ben Mhenni, Sébastien Bourguignon, Marcel Mongeau, Jordan Ninin, Hervé Carfantan. Sparse Branch and Bound for Exact Optimization of L0-Norm Penalized Least Squares. ICASSP 2020, IEEE International Conference on Acoustics, Speech and Signal Processing, May 2020, Barcelona, Spain. pp.ISBN: 978-1-5090-6632-2, ⟨10.1109/ICASSP40776.2020.9053870⟩. ⟨hal-02564594⟩