Sparse Branch and Bound for Exact Optimization of L0-Norm Penalized Least Squares
Ramzi Ben Mhenni, Sébastien Bourguignon, Marcel Mongeau, Jordan Ninin, Hervé Carfantan
Abstract
We propose a global optimization approach to solve ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> -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 ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -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.
BibTeX
@inproceedings{icassp2020_sparsebranchandb,
title = {Sparse Branch and Bound for Exact Optimization of L0-Norm Penalized Least Squares},
author = {Ramzi Ben Mhenni and Sébastien Bourguignon and Marcel Mongeau and Jordan Ninin and Hervé Carfantan},
booktitle = {ICASSP 2020},
year = {2020}
}