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
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 L_{0}-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.
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:
First, register as an academic (if so) here http://www-304.ibm.com/ibm/university/academic/pub/page/mem_join
Once your registration has been approved (it can take up to several days), you can dowload the IBM ILOG CPLEX Optimization Studio installer. Instructions are here: https://www-304.ibm.com/ibm/university/academic/member/softwaredownload
Finally, a few configurations are required to run CPLEX under Matlab: http://www-01.ibm.com/support/knowledgecenter/SSSA5P_12.6.2/ilog.odms.cplex.help/CPLEX/MATLAB/topics/gs_install.html
Then, the archive MIP_programs.rar contains Matlab programs implementing nine different optimization problems with CPLEX:
optiMIP_minL1_constL0.m, optiMIP_minL2_constL0.m and optiMIP_minLinf_constL0.m perform optimization of sparsity-constrained problems, where an L_{1}-norm (respectively, L_{2}- and L_{∞}-norm) error term is minimized under a maximum value of the L_{0} norm of the unknown vector;
optiMIP_minL0_constL1.m, optiMIP_minL0_constL2.m and optiMIP_minL0_constLinf.m perform optimization of data-misfit-constrained problems, where the L_{0}-norm of the unknown vector is minimized under a maximum value of the L_{1}-norm (respectively, L_{2}- and L_{∞}-norm) of the error term;
finally, optiMIP_minL0plusL1.m, optiMIP_minL0plusL2.m and optiMIP_minL0plusLinf.m perform optimization of penalized problems, where the weighted sum of the L_{0}-norm of the unknown vector and the L_{1}-norm (respectively, L_{2}- and L_{∞}-norm) of the error term is minimized.
Every function is called with a similar syntax:
[x,M,exitflag,output] = optiMIP_***(y,H,param,x0,M,options);
where:y is the data vector;
H is the dictionary;
param is the specific parameter for each formulation: maximum value of the L_{0} norm for sparsity-constrained formulations (K in the paper), maximum value of the L_{p}-norm of the error term for data-misfit-constrained problems (α_{p} in the paper) and penalty parameter for penalized problems (μ_{p} in the paper), which weights the L_{0}-norm term);
x0 sets the initial value of x;
M sets the initial value of parameter M required for the bigM reformulation;
options is a structure defining CPLEX solver options (see here for details).
The last three parameters are optional. If not specified, x0 is set to the zero vector, M is set to 1.1 ‖ H^{T} 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:
x, the solution found by the solver;
M, the value for the bigM reformulation that was used, which satisfies ‖ x ‖ _{∞} < M;
exitflag is an integer identifying the reason why the optimization algorithm terminated;
output is a structure containing information about the optimization process.
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 .