Sparse Branch And Bound For Exact Optimization Of L0-Norm Penalized Least Squares

We propose a global optimization approach to solve l_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 l_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.