@article{bou-nin-car-mon-16-aa-sparse,
  author = {Bourguignon, S{\'e}bastien and Ninin, Jordan and Carfantan, Herv{\é} and Mongeau, Marcel},
  title = {Exact Sparse Approximation Problems via Mixed-Integer Programming: Formulations and Computational Performance}, 
  journal = {IEEE Transactions on Signal Processing}, 
  year = 2016,
  volume = 64,
  number = 6,
  pages = {1405-1419},
  doi = {10.1109/TSP.2015.2496367},
  issn = {1941-0476},
  month = mar,
  Comment = {Does it use AA? Not clear. But linear programming approximation may be related.},
  altkeys = {bou-nin-car-mon-15-aa-sparse},
  abstract = {Sparse approximation addresses the problem of approximately fitting a linear model with a solution having as few non-zero components as possible. While most sparse estimation algorithms rely on suboptimal formulations, this work studies the performance of exact optimization of $l_0$-norm-based problems through Mixed-Integer Programs (MIPs). Nine different sparse optimization problems are formulated based on $l_1$, %$_2$ or $l_{\infinity}$ data misfit measures, and involving whether constrained or penalized formulations. For each problem, MIP reformulations allow exact optimization, with optimality proof, for moderate-size yet difficult sparse estimation problems. Algorithmic efficiency of all formulations is evaluated on sparse deconvolution problems. This study promotes error-constrained minimization of the $l_0$ norm as the most efficient choice when associated with $l_1$ and $l_{\infinity}$ misfits, while the $l_2$ misfit is more efficiently optimized with sparsity-constrained and sparsity-penalized problems. Exact $l_0$-norm optimization is shown to outperform classical methods in terms of solution quality, both for over- and underdetermined problems. Numerical simulations emphasize the relevance of the different lp fitting possibilities as a function of the noise statistical distribution. Such exact approaches are shown to be an efficient alternative, in moderate dimension, to classical (suboptimal) sparse approximation algorithms with $l_2$ data misfit. They also provide an algorithmic solution to less common sparse optimization problems based on $l_1$ and $l_{\infinity}$ misfits. For each formulation, simulated test problems are proposed where optima have been successfully computed. Data and optimal solutions are made available as potential benchmarks for evaluating other sparse approximation methods.}
}