SEMINAIRE DU 2 JUIN 2016 – 15H @ LTCI – C49
On fast transform optimization
We study a strategy to optimize sparse convolution kernels leaving on the edges of a tree. They define a fast transform and target atoms prescribed by the user. The so-constructed (deep) optimization problem is smooth but might be strongly non-convex. Experiments shows that fast transforms can be optimized and opens many perspectives.
François Malgouyres is Professor at Institut de Mathématiques de Toulouse.
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 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
SEMINAIRE DU 7 mai 2015 – 16H @ LTCI – AMPHI SAPHIR
A Texton for Fast and Flexible Gaussian Texture Synthesis
Gaussian textures can be easily simulated by convolving an image sample with a conveniently normalized white noise. However, this procedure is not very flexible (it does not allow for non-uniform grids in particular), and becomes computationally heavy for very large domains. A Gaussian texture can also be approximated by a high-intensity discrete spot noise (DSN), obtained by summing randomly-shifted copies of a kernel along the points of a Poisson process.
In this talk, we propose an algorithm that summarizes a texture sample into a synthesis-oriented texton, that is, a small image for which the DSN simulation is more efficient than the classical convolution algorithm. Using this synthesis-oriented texture summary, Gaussian textures can be generated on-demand in a faster, simpler, and more flexible way.
Project Page (Synthesis-Oriented Texton)
Arthur Leclaire is finishing his PhD Thesis and working as a young teacher and researcher at Université Paris-Descartes and ENS Cachan.