Efficient algorithms for nonsmooth optimization in imaging

This joint French-Austrian research project is concerned with the development of efficient algorithms for solving nonsmooth optimization problems arising in imaging. Solving these problems is very challenging, since the objective function is very often non-differentiable and the number of unknowns is usually very large. Hence, standard algorithms such as gradient methods or Newton simply fail. Recently, there has been an increased interest in so-called proximal-like methods. Although developed already in the seventies, they have been revitalized just because of their ability to deal with large nonsmooth problems. Although in principle slower than more sophisticated algorithms such as interior point methods, their simplicity makes them particularly well suited to be implemented on highly parallel architectures, such as GPUs. This can lead to a drastic performance gain - usually a factor of 30 or more. Very recent results indicate that a specific class of proximal-like algorithms - so called first- order primal-dual algorithms - are particularly promising. On the one hand they can deal with a reasonably large class of structure convex problems and on the other hand they seem to be particularly well suited to solve large nonsmooth problems. Despite their good performance, there are still many open problems that need to be addressed in order to further improve these algorithms. Interesting questions include the optimal preconditioning, the optimal acceleration on smoother problems and the application to very large-scale problems. Finding answers to these questions would mean solving larger problems in shorter time, which in turn would allow researchers to investigate more complex and hence more realistic models.

The main objective of the EANOI project was to maintain and enforce a long standing research collaboration between the two groups, of Thomas Pock at Graz University of Technology, Austria and Antonin Chambolle at Ecole Polytechnique, Palaiseau, France. The main research direction was the development of numerical optimization algorithms for various problems in image processing and computer vision. This includes important problems such as image restoration, image segmentation, image reconstruction, stereo, optical flow and many more. The goal of the project was to develop research in these areas, as well as training students in these fields. Optimization is a old an broad topic but its application to image-related problems requires the development of specialized methods that can deal with the large amount of optimization variables (very often in the range of several millions) and with the non-smooth structure of the optimization problems. In such cases it is simply impossible to apply sophisticated solvers from commercial software packages and hence, one has to adopt simpler methods such as gradient-based algorithms. An important an hot topic in large-scale optimization is therefore to improve (or accelerate) such simple gradient-based methods in terms of their numerical efficiency. The main outcome of the EANOI project is as follows: (i) We have provided a general convergence analysis of a first-order primal-dual algorithm for solving non-smooth optimization problems with known saddle-point structure. (ii) We have given a first convergence proof of the iterations of an important accelerated proximal gradient method, known as FISTA. (iii) We have analyzed so-called inertial gradient methods in both the convex and non-convex setting, which lead to significantly faster convergence while keeping the complexity of the algorithm basically unchanged. (iv) We have published a long review paper about continuous optimization for imaging in the Acta Numerica journal, which is one most prestigious journal in the field of numerical mathematics.