15 Marzo, 2012 15:00 oclock

Inverse free-discontinuity problems and iterative thresholding algorithms

Massimo Fornasier, Technical University of Munich, Germany

Aula Seminari Saleri , VI Piano, MOX - Dipartimento di Matematica Politecnico di Milano

Free-discontinuity problems describe situations where the solution of interest is defined by a function and a lower dimensional set consisting
of the discontinuities of the function. Hence, the derivative of the solution is assumed to be a small function almost everywhere except on
sets where it concentrates as a singular measure. This is the case, for instance, in certain digital image segmentation problems and brittle
fracture models. In the first part of this talk we show some counterexamples to existence of minimizers of functionals modeling inverse free-discontinuity problems. New preliminary results on the existence of minimizers are then obtained, by restricting the solutions
to a class of functions with piecewise Lipschitz discontinuity set. If we discretize such situations for numerical purposes, the inverse
free-discontinuity problem in the discrete setting can be re-formulated as that of finding a derivative vector with small components at all but a few entries that exceed a certain threshold. This problem is similar to those encountered in the field of sparse recovery , where vectors with a small number of dominating components in absolute value are
recovered from a few given linear measurements via the minimization of related energy functionals. We first show results of existence of minimizers in the discrete setting of inverse free-discontinuity problems and then we show that their computation is actually NP-hard.
With the aim of formulating efficient computational approaches in such a complicated situation, we address iterative thresholding algorithms which intertwine gradient-type iterations with thresholding steps which
were designed to recover sparse solutions. It is natural to wonder how such algorithms can be used towards solving discrete free-discontinuity
problems. This talk explores also this connection, and, by establishing an iterative thresholding algorithm for discrete inverse
free-discontinuity problems, provides new insights on properties of minimizing solutions thereof.