  The Sparse Approximation problem asks to find a solution $x$ such that $||y -
Hx|| < \alpha$, for a given norm $||\cdot||$, minimizing the size of the
support $||x||_0 := \#\{j \ |\ x_j \neq 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.
