Évènement

Date(s) : 16/01/2015   iCal
14h00 - 15h00

Exact minimisation of L0-based sparse approximation criteria through mixed integer programming\n\nby S. Bourguignon (IRRCYN)\n\nSparse approximation addresses the problem of solving approximately a given system of linear equations y = Ax with a vector x having as few non-zero components as possible. It formulates a bi-objective optimization problem\, where both a discrepancy function and the L0-« norm » sparsity measure are minimized. Optimization is essentially combinatorial and is often tackled through the convex relaxation of the L0 norm\, or by heuristic combinatorial exploration techniques. Optimality conditions then rely on prior assumptions on near-orthogonality of A and on sufficient sparsity of the solution x.\nIn many inverse problems\, such conditions are not satisfied and the aforementioned methods clearly fail in locating the global minimum. We study global optimization methods of the L0-norm sparse approximation problem based on Mixed Integer Programming\, which involves both continuous and integer variables. Different problem formulations are proposed. We show that exact optimization of such problems is possible on certain moderate size inverse problems\, whereas usual methods fail in locating sparsest solutions and exhaustive enumeration remains prohibitive. The resulting formulations are studied in terms of computational efficiency\, and simulations evaluate the support identification capacities of the different Lp-fitting-based formulations in the presence of noise\, depending on the noise statistical distribution. Finally\, an application to spike train deconvolution in ultrasonic non-destructive testing is presented.\n\n

Catégories Pas de Catégories