2019 | SW2SB

Sparse Wars. Episode II : Parsimony battles

Axe & tâche scientifique DigiCosme : ComEx
Coordinateurs : Leo Liberti, LIXMatthieu Kowalski, L2S
Chercheur postdoctoral :
Adresse mail :
Laboratoire gestionnaire: LIX

Institution : Polytechnique
Adossé à l’action DigiCosme : GT Theorie de l’Information

Durée : 1 an
(2019 – 2020)


The most general possible representation of signals is that of continuous functions f(t) of time. This model is not helpful when one needs to handle signal in practice. Instead, signals are acquired, manipulated, and delivered as a discrete set of time-indexed samples. Thus, the fundamental problem is that of reconstructing a continuous function from a discrete set of its points. The crucial observation making this reconstruction possible is that useful signals have a very different (and special) structure with respect to noise.


In this project we work with parsimony sampling. The simplest type of parsimony sampling is also known as compressive sampling (or compressed sensing), which is based on the observation that some linear transformations of most practical signals lead to functions with sparse support.

Productions Scientifiques

  1. Diego Delle Donne, Matthieu Kowalski, Leo Liberti, MIP based approaches to the Sparse Approximation problem, Proceedings of ROADEF 2020
  2. Delle Donne D., Kowalski M. and Liberti L., Mixed Integer Programming techniques applied to L0 minimization problems. INRIA Parietal team seminar, June, 2020
  3. Diego Delle Donne, Matthieu Kowalski, Leo Liberti, MIP and set covering approaches to sparse approximation, Proceedings of iTWIST 2020
  4. Delle Donne D., Kowalski M. and Liberti L., A novel integer linear programming approach for global L0 minimization. SIAM Journal on Optimization. Submitted.
  5. Diego Delle Donne, Matthieu Kowalski, Leo Liberti, Sparse Wars. Episode II: Parsimony battles: Final Report, technical report, 2020