Sébastien Bourguignon
logoECN logoLS2N

Assistant professor
École Centrale de Nantes (ECN) / Laboratoire des Sciences du Numérique de Nantes (LS2N)
Research Team SIMS (Signal, Image and Sound)
Office S-207
Phone (33) 2 40 37 69 15
Sebastien dot Bourguignon at ec-nantes.fr


Exact optimisation of L0-norm-based sparse approximation criteria through mixed-inter programming: programs and test cases

Material related to paper: S. Bourguignon, J. Ninin, H. Carfantan and M. Mongeau, Exact sparse approximation problems via mixed-integer programming: Formulations and computational performance, IEEE Transactions on Signal Processing, 64(6):1405--1419, March 2016. [ .pdf ]

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 project studies the performance of exact optimization of L0-norm-based problems through Mixed-Integer Programs (MIPs). First results have shown that some moderate-size sparse approximation inverse problems can be solved exactly, whereas exhaustive search remains computationally prohibitive for such instances and usual (suboptimal) sparse estimation problems fail in locating the global optimum.

The following codes are Matlab implementations for solving several formulations of sparse approximation problems using the IBM ILOG CPLEX MIP solver. If optimization terminates successfully, then the solution is guaranteed to be a global minimizer of the optimization problem. It can be used, either to solve a given formulation of sparse approximation, or to evaluate any other sparse approximation algorithm. Simulated test problems are also provided as multimedia attachements to the paper, which can be dowloaded here .

Note that such programs are intented to be tested on relatively small-size problems, say, with a few hundreds of unknowns. In particular, solving the quadratically-constrained formulation is rather inefficient, see Table 2 in the above referenced paper.

Please send me an e-mail for any comment or question.

Programs

In order to use the following programs, you first need to install CPLEX. CPLEX is free of use for education and research purposes, but requires registration:

Then, the archive MIP_programs.rar contains Matlab programs implementing nine different optimization problems with CPLEX:

Every function is called with a similar syntax:

[x,M,exitflag,output] = optiMIP_***(y,H,param,x0,M,options);

where:

The last three parameters are optional. If not specified, x0 is set to the zero vector, M is set to 1.1 ‖ HT y ‖ (where columns in H are unit-norm), and options are default CPLEX options, except the maximum time allowed which is set to options.MaxTime = 1000 s.

Optimization is run with a maximum time allowed set by parameter options.MaxTime. If the bound M is reached by some component of the solution, then the MIP reformulation is not valid and optimization is run again with M replaced with 1.1M, until the obtained solution satisfies ‖ x ‖ < M. It returns:

The last two outputs are provided by CPLEX. Details on their content can be found, e.g., here .

Test cases

Test cases are provided as multimedia material attached to the paper:

S. Bourguignon, J. Ninin, H. Carfantan and M. Mongeau, Exact sparse approximation problems via mixed-integer programming: Formulations and computational performance, IEEE Transactions on Signal Processing, 64(6):1405--1419, March 2016. [ .pdf ]

The Matlab files and a description of their content are here .