Creating and sharing knowledge for telecommunications

Project: Beyond Convexity: Non-Convex Optimization and Game-Theoretic Approaches for Imaging Inverse Problems

Acronym: PAConvex
Main Objective:
Imaging inverse problems (IIPs) abound in the modern world. Medical imaging (CT, MRI, PET, ultrasound), remote sensing, seismography, non-destructive inspection, digital photography, astronomy, all involve at their computational core the solution of IIPs: they produce visual representations (images) of an underlying reality from indirect/imperfect observations. In a nutshell, the goal of this project is to advance the state of the art in computational methods for IIPs, by exploiting the promising new possibilities that lie outside of the classical convex optimization approaches.

IIPs are ill-posed: even if the observation operator is perfectly known, the observations do not uniquely and stably determine the solution. This difficulty is dealt with by seeking a compromise between data fidelity (fitting the observed data) and adherence to properties that the unknown image is known/desired to have. The classical way to seek this balance is to formulate an optimization problem (usually convex, more by reasons of mathematical tractability than model adequacy), where the objective function includes a term encouraging data fidelity and another (the regularizer/prior) penalizing undesirable solutions; in this approach, convex optimization takes center stage and has been in the limelight of computational imaging.

If the observation operator is only partially known (in the so-called blind problems), the goal is to infer, not only the underlying image, but also the missing information about the observation model. Blind problems are obviously more ill-posed, requiring regularizers/priors that better model the images of interest. Moreover, variational formulations of blind IIPs are naturally non-convex, thus out of reach for the efficient convex optimization tools developed in the past decade for the convex formulations of non-blind IIPs. Consequently, the methods that have been proposed for blind problems lack convergence guarantees and require "tricks" in order to work well (e.g., careful initialization and continuation procedures), making it hard to trace their (non)success to the behavior of the optimization algorithm or the (in)adequacy of the objective function.

Non-convexity also stems from using non-convex regularizers, even in non-blind IIPs, e.g., constraints/penalties on the number of coefficients that represent the image on some frame or dictionary. These non-convex regularizers are central in the recent theory of compressive sensing and much research has been devoted to finding conditions under which similar solutions are obtained with convex relaxations. Very recently, algorithms that directly tackle the non-convex formulations have been proposed by exploiting particular properties of the observation operator, namely their restricted isometry properties (RIP). However, in IIPs, the RIP is essentially impossible to guarantee, making the application of these non-convex approaches an open research front.

This project aims at advancing the state of the art in computational methods for IIPs, by departing from the convex optimization realm and its limitations, in several directions:

a) We will investigate optimization methods for non-convex formulations of blind IIPs; unlike previous approaches, we seek methods with theoretical guarantees and without careful user interaction. Of course, non-convex optimization can only be approached by exploiting specific characteristics of the class of problem in hand; this is precisely the strategy we will follow. In particular, a recently proposed new class of algorithms for non-convex structured functions, based on the Kurdyka-Lojasiewicz property, is a promising tool for this quest.

b) We will develop algorithms for non-convex regularization, by exploiting the lines of attack that have recently been successfully followed for compressed sensing (CS). However, unlike in CS, the observation operators in general IIPs do not exhibit RIP, thus other characterizations are needed to support the sought for theoretical guarantees.

c) For blind IIPs, we will seek formulations of the compromise between data fitness and regularization as equilibrium (rather than optimization) problems, namely via variational inequalities (VIs) and game theory. Since optimization problems are particular cases of VIs but the reciprocal is not true, this approach contains and extends the standard optimization formulation, opening the door to more general criteria and computational methods. For example, blind deblurring can be formulated as an equilibrium problem (a game) between estimating the underlying image and estimating the blur.
Reference: PTDC/EEI-PRO/1470/2012
Funding: FCT
Start Date: 01-06-2013
End Date: 01-06-2015
Team: Mario Alexandre Teles de Figueiredo, José Manuel Bioucas Dias, Luís Henrique Martins Borges de Almeida, João Pedro Afonso Oliveira da Silva, Miguel Antunes Dias Alfaiate Simões, Xiangrong Zeng
Groups: Pattern and Image Analysis – Lx
Local Coordinator: Mario Alexandre Teles de Figueiredo
Links: Internal Page
Associated Publications