ERC FUNDED PROJECTS

Interior point algorithms and a dramatic growth in computing power have revolutionized optimization in the last two decades. Highly nonlinear problems which were previously thought intractable are now routinely solved at reasonable scales. Semidefinite programs (i.e. linear programs on the cone of positive semidefinite matrices) are a perfect example of this trend: reasonably large, highly nonlinear but convex eigenvalue optimization problems are now solved efficiently by reliable numerical packages. This in turn means that a wide array of new applications for semidefinite programming have been discovered, mimicking the early development of linear programming. To cite only a few examples, semidefinite programs have been used to solve collaborative filtering problems (e.g. make personalized movie recommendations), approximate the solution of combinatorial programs, optimize the mixing rate of Markov chains over networks, infer dependence patterns from multivariate time series or produce optimal kernels in classification problems. These new applications also come with radically different algorithmic requirements. While interior point methods solve relatively small problems with a high precision, most recent applications of semidefinite programming in statistical learning for example form very large-scale problems with comparatively low precision targets, programs for which current algorithms cannot form even a single iteration. This proposal seeks to break this limit on problem size by deriving reliable first-order algorithms for solving large-scale semidefinite programs with a significantly lower cost per iteration, using for example subsampling techniques to considerably reduce the cost of forming gradients. Beyond these algorithmic challenges, the proposed research will focus heavily on applications of convex programming to statistical learning and signal processing theory where optimization and duality results quantify the statistical performance of coding or variable selection algorithms for example. Finally, another central goal of this work will be to produce efficient, customized algorithms for some key problems arising in machine learning and statistics.

1 148 460 €

Start date: 2011-05-01, End date: 2016-04-30

The goal of this project is to study the topology of Stein manifolds from the viewpoint of symplectic and contact geometry. It addresses the fundamental questions of the subject: - How does the Lagrangian skeleton of a Stein manifold determine the Stein structure? - To what extent the study of Stein structures can be reduced to a combinatorial study of the skeleton? - How are the symplectic invariants of Stein manifolds, respectively the contact invariants of their boundary, determined by the skeleton? For the topological part, we will use as a source of inspiration the theory of spines and shadows of 3- and 4- manifolds. One of the goals of this research project is to adapt it to the setup of Stein manifolds and develop a calculus of Lagrangian shadows. Concerning invariants of contact manifolds, we aim to interpret symplectic homology of Stein manifolds and contact homology of their boundaries in topological terms, with the skeleton playing a central role. Further ramifications of this research project include the development of string topology on singular (stratified) spaces and the symplectic study of singularities.

1 053 101 €

Start date: 2010-09-01, End date: 2016-08-31

We propose to investigate traffic phenomena from the macroscopic point of view, using models derived from fluid-dynamics consisting in hyperbolic conservation laws. In fact, even if the continuum hypothesis is clearly not physically satisfied, macroscopic quantities can be regarded as measures of traffic features and allow to depict the spatio-temporal evolution of traffic waves. Continuum models have shown to be in good agreement with empirical data. Moreover, they are suitable for analytical investigations and very efficient from the numerical point of view. Therefore, they provide the right framework to state and solve control and optimization problems, and we believe that the use of macroscopic models can open new horizons in traffic management. The major mathematical difficulties related to this study follow from the mandatory use of weak (possibly discontinuous) solutions in distributional sense. Indeed, due to the presence of shock waves and interactions among them, standard techniques are generally useless for solving optimal control problems, and the available esults are scarce and restricted to particular and unrealistic cases. This strongly limits their applicability. Our scope is to develop a rigorous analytical framework and fast and efficient numerical tools for solving optimization and control problems, such as queues lengths control or buildings exits design. This will allow to elaborate reliable predictions and to optimize traffic fluxes. To achieve this goal, we will move from the detailed structure of the solutions in order to construct ad hoc methods to tackle the analytical and numerical difficulties arising in this study. The foreseen applications target the sustainability and safety issues of modern society.

809 000 €

Start date: 2010-10-01, End date: 2016-03-31

Digital video is everywhere, at home, at work, and on the Internet. Yet, effective technology for organizing, retrieving, improving, and editing its content is nowhere to be found. Models for video content, interpretation and manipulation inherited from still imagery are obsolete, and new ones must be invented. With a new convergence between computer vision, machine learning, and signal processing, the time is right for such an endeavor. Concretely, we will develop novel spatio-temporal models of video content learned from training data and capturing both the local appearance and nonrigid motion of the elements---persons and their surroundings---that make up a dynamic scene. We will also develop formal models of the video interpretation process that leave behind the architectures inherited from the world of still images to capture the complex interactions between these elements, yet can be learned effectively despite the sparse annotations typical of video understanding scenarios. Finally, we will propose a unified model for video restoration and editing that builds on recent advances in sparse coding and dictionary learning, and will allow for unprecedented control of the video stream. This project addresses fundamental research issues, but its results are expected to serve as a basis for groundbreaking technological advances for applications as varied as film post-production, video archival, and smart camera phones.

2 454 090 €

Start date: 2011-01-01, End date: 2016-12-31