2020/09/14 by Diego Delle Donne, Donne, Diego Delle, Matthieu Kowalski +3
Business, Management and Accounting · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Facility Location and Emergency Management #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2009.06312
openalex publication_date 2020/09/14 · openalex created_date 2020/09/21 · openalex updated_date 2026/07/28
The Sparse Approximation problem asks to find a solution x such that ||y - Hx|| < α, for a given norm ||⋅||, minimizing the size of the support ||x||0 := #\j | xj ≠ 0 \. We present valid inequalities for Mixed Integer Programming (MIP) formulations for this problem and we show that these families are sufficient to describe the set of feasible supports. This leads to a reformulation of the problem as an Integer Programming (IP) model which in turn represents a Minimum Set Covering formulation, thus yielding many families of valid inequalities which may be used to strengthen the models up. We propose algorithms to solve sparse approximation problems including a branch & cut for the MIP, a two-stages algorithm to tackle the set covering IP and a heuristic approach based on Local Branching type constraints. These methods are compared in a computational experimentation with the goal of testing their practical potential.