MIP and Set Covering approaches for Sparse Approximation

Diego Delle Donne, Matthieu Kowalski, Leo LibertiarXiv 2020 · arXiv

Abstract

Sparse approximation is a fundamental challenge in signal processing and data science, requiring the representation of a signal using the fewest possible components from a dictionary. While traditionally modeled using Mixed-Integer Programming (MIP) with "Big-M" constraints, these formulations often suffer from weak mathematical relaxations and numerical instability. This paper introduces a novel reformulation of the sparse approximation problem as a Set Covering problem. By identifying "forbidden supports"—subsets of dictionary columns that cannot satisfy the error threshold—the authors derive valid inequalities that characterize the feasible support space. This approach allows for the application of combinatorial optimization techniques, bypassing the numerical pitfalls of Big-M constraints and providing a theoretical bridge between signal processing and set covering literature.

Introduction

In the field of signal processing, sparse approximation involves finding a vector $x$ such that a target signal $y$ is approximated by a dictionary $H$ (where $y \approx Hx$) using a minimal number of non-zero entries in $x$. Mathematically, this is the minimization of the $\ell_0$ "norm," subject to a reconstruction error constraint $||y - Hx|| \le \alpha$.

Because the $\ell_0$ norm is discrete and non-convex, the problem is NP-hard. The standard optimization approach utilizes Mixed Integer Programming (MIP). However, traditional MIP formulations rely on "Big-M" constraints—large constants used to link binary selection variables to continuous coefficients. These constants often lead to "weak" relaxations where the solver's lower bound improves very slowly, resulting in prohibitive computation times for large-scale or ill-conditioned instances. This paper proposes a departure from Big-M formulations by treating the problem through the lens of combinatorial Set Covering.

The Set Covering Reformulation

The core innovation of this work is the mapping of sparse approximation onto a Set Covering framework. The authors achieve this by focusing on the support of the solution—the set of indices of the non-zero coefficients—rather than the coefficients themselves.

Forbidden Support Inequalities

The authors define a "forbidden support" as any subset of columns from the dictionary $H$ that, even in their best linear combination, fail to approximate the signal $y$ within the error tolerance $\alpha$. For every such forbidden support, a valid inequality can be generated: to reach a feasible solution, the optimizer must select at least one column that is not in that forbidden set.

Crucially, the paper proves that these forbidden support inequalities are not merely supplemental; they are sufficient to describe the entire space of feasible supports. This allows the sparse approximation problem (specifically for $\ell_1$ and $\ell_\infty$ error norms) to be viewed as a pure Set Covering Problem (SCP).

Algorithmic Framework

Since the number of possible forbidden supports grows exponentially with the size of the dictionary, they cannot be enumerated a priori. The authors propose a two-stage exact algorithm and a supporting heuristic:

  1. Two-Stage Exact Solver: The algorithm begins by solving a relaxed version of the problem. It then checks the feasibility of the resulting support using a simple Linear Program (LP). If the support is found to be "forbidden," a new cut (a forbidden support inequality) is added to the master problem, and the process repeats. This "branch-and-cut" style approach avoids Big-M constraints entirely during the integer search.
  2. Local Branching Heuristic: To accelerate the discovery of high-quality solutions, the authors implement a Local Branching heuristic. This method restricts the search to a neighborhood around a known solution (defined by a distance $\delta$). If no better solution is found within that radius, the search area is incrementally expanded. This allows the solver to find "good enough" sparse representations quickly, which can then be used to prune the search tree in the exact algorithm.

Theoretical Insights and Results

The paper provides a rigorous theoretical foundation for this cross-disciplinary approach:

  • Polyhedral Results: Proposition 2.2 demonstrates that the projection of the original MIP onto the space of binary variables is exactly a set-covering polytope. This allows the use of specialized facets and valid inequalities derived from decades of SCP research.
  • New Valid Inequalities: By leveraging the SCP connection, the authors derive a new family of complex valid inequalities (Proposition 2.3). These inequalities further tighten the problem representation, making it easier for modern solvers to process.
  • Numerical Potential: While the paper focuses on the theoretical framework and omits extensive benchmarking tables due to space constraints, the authors report that the Local Branching heuristic shows significant promise in handling "pathological" instances that are traditionally difficult for standard solvers like CPLEX or Gurobi.

Limitations and Future Directions

While the Set Covering approach provides a powerful new toolset, it currently has specific limitations:

  • Norm Specificity: The current formulation is optimized for $\ell_1$ and $\ell_\infty$ misfit measures. Extending this framework to the $\ell_2$ (Euclidean) norm—the most common measure in signal processing—is more challenging because it introduces quadratic constraints into the feasibility check.
  • Computational Benchmarking: Future work is required to provide a comprehensive numerical comparison against state-of-the-art MIP solvers across a wider variety of datasets.

By bridging the gap between combinatorial optimization and signal processing, this research opens new avenues for solving sparse approximation problems exactly, moving beyond the numerical limitations of traditional Big-M modeling.

Summary updated

Abstract

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.
BibTeX
@misc{donne2020mip,
  author = {Diego Delle Donne and Matthieu Kowalski and Leo Liberti},
  title = {{MIP and Set Covering approaches for Sparse Approximation}},
  year = {2020},
  eprint = {2009.06312},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.06312},
}
Figure