Sorry, this entry is only available in French.
SEMINAIRE DU 1 OCTOBRE 2015 – 15H @ LTCI – SALLE C49
Finite identification and local linear convergence of proximal splitting algorithms.
Convex nonsmooth optimization has become ubiquitous in most quantitative disciplines of science. Proximal splitting algorithms are very popular to solve structured convex optimization problems. Within these algorithms, the Forward-Backward and its variants (e.g. inertial FB, FISTA, Tseng’s FBF), Douglas-Rachford and ADMM are widely used. The goal of this work is to investigate the local convergence behavior of these schemes when the involved functions are partly smooth relative to the associated active manifolds. In particular, we show that (i) all the aforementioned splitting algorithms correctly identify the active manifolds in a finite number of iterations (finite activity identification), and (ii) then enter a local linear convergence regime, which we characterize precisely in terms of the structure of the involved active manifolds. For problems involving quadratic and polyhedral functions, we show how to get finite termination of Forward-Backward-type splitting. These results may have numerous applications including in signal/image processing, sparse recovery and machine learning. Indeed, the obtained results explain the typical behaviour that has been observed numerically for many problems in these fields such as the Lasso, the group Lasso, the fused Lasso and the nuclear norm regularization to name only a few.
Jalal Fadili is Professor of Image and Signal Processing at ENSICAEN and a junior member of Institut Universitaire de France.
SEMINAIRE DU 1 octobre 2015 – 16H @ LTCI – Salle C49
Low-Rank Video Segmentation for Background Estimation, and Multi-Temporal Foreground Detection in Videos
Background and foreground separation in videos is a ubiquitous task in many computer vision problems such as object recognition to tracking, and consequently much work has been done on this subject.
Recently, Candès et al. showed that such an estimation task could be addressed as a convex optimisation problem. The framework which they proposed is called Robust Principle Component Analysis (RPCA), and separates a matrix into the sum of a low-rank matrix (the background) and a sparse matrix (the foreground). The low-rank nature of the first matrix means that global lighting changes are handled. In this talk, we adapt and improve upon this framework in two ways.
Firstly, we propose an algorithm to achieve a “local” version of RPCA. Indeed, a considerable drawback of the standard RPCA is its poor ability to handle local lighting changes. We propose to model the background as piece-wise low-rank, each “piece” corresponding to spatio-temporally localised lighting conditions. The main challenge in this task is to identify the coherent regions, which we do with a region-merging approach based on spectral (graph) clustering. We show that this local RPCA allows for greater robustness to both local lighting changes and foreground elements which may remain static for a certain time.
Secondly, we present an online version of RPCA for the task of detecting foreground at multiple timescales. The goal of this analysis is to identify objects which remain in a certain position for a (user-defined) timescale. With visual examples, we show that this algorithm can be used for applications such as detecting the fluidity of traffic or detecting immobile people who may require assistance.
Alasdair Newson is currently a postdoctoral researcher at Université Paris-Descartes.
SEMINAIRE DU 4 JUIN 2015 – 16H @ MAP5 – SALLE DU CONSEIL
Joint phase denoising and unwrapping for 3D reconstruction in
multi-channel SAR interferometry: combining patch-based non-local
filtering and total variation regularization
SAR (Synthetic Aperture Radar) systems are powerful imaging systems allowing height retrieval thanks to interferometric phase measurements (InSAR). While a single interferometric phase implies a phase unwrapping step, multi-channel InSAR systems reduce ambiguities for height retrieval but still provide very noisy measurements.
In this work we investigate how the combination of patch-based approaches and total variation minimization (TV) improve 3D InSAR reconstruction.
After a brief introduction to SAR imagery and InSAR acquisition, the adaptation of non-local methods to complex vectorial data will be presented. Then a non local likelihood term is introduced in the TV regularization framework, and optimized thanks to a graph-cut minimization approach. Results on synthetic and real InSAR data will be discussed.
This work is a joint work with C. Deledalle (IMB), L. Denis (Laboratoire Hubert Curien), and G. Ferraioli (Parthenope University, Naples, Italy).
SEMINAIRE DU 7 mai 2015 – 15H @ LTCI – Amphi Saphir
Primal-dual forward-backward splitting for large-scale convex optimization
A wide array of estimation and restoration problems, in particular inverse imaging problems, can be formulated as large-scale convex optimization problems in Hilbert spaces: the goal is to minimize a sum of convex functions, possibly composed with linear operators. The forward-backward splitting technique, when applied in primal-dual product spaces, is a powerful umbrella that encompasses the classical forward-backward, Douglas-Rachford, and Chambolle-Pock algorithms. A useful extension with variable metric is discussed. Some applications in imaging are shown.
Laurent Condat is a permanent CNRS researcher at GIPSA-lab (Grenoble, France).
- L. Condat, “A Generic Proximal Algorithm for Convex Optimization – Application to Total Variation Minimization,” IEEE Signal Proc. Letters, vol. 21, no. 8, pp. 1054-1057, Aug. 2014. PDF. Matlab files: optimization.zip
- L. Condat, “A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms,” J. Optimization Theory and Applications, vol. 158, no. 2, pp. 460-479, 2013. PDF
- L. Condat, “A direct algorithm for 1D total variation denoising,” IEEE Signal Proc. Letters, vol. 20, no. 11, pp. 1054-1057, Nov. 2013. PDF. C file: condat_fast_tv.c