Optimisation Géométrique sur les Variétés

Nous vous rappelons que, afin de garantir l'accès de tous les inscrits aux salles de réunion, l'inscription aux réunions est gratuite mais obligatoire.

Inscriptions closes à cette réunion.

Inscriptions

25 personnes membres du GdR ISIS, et 24 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 100 personnes.

Annonce

Programme

9h00-9h45: P.-A. Absil (UC Louvain)
Optimization and curve fitting on manifolds.

9h45-10h15: N. Boumal (ENS Ulm)
Manopt, a Matlab toolbox for optimization on manifolds.

10h15-10h45: Pause

10h45-11h30: S. Bonnabel (Mines ParisTech)
Méthodes de gradient stochastique sur les variétés riemanniennes.

11h30-12h00: M. Bacak (Telecom ParisTech)
Proximal point algorithm in Hadamard spaces.

12h00-12h30: P.-Y. Gousenbourger (UC Louvain)
Interpolation on Riemannian manifolds with a C1 piecewise-Bézier curves.

12h30-14h: Pause déjeuner

14h00-14h45: A. Trouvé (ENS Cachan)
Geodesic shooting in shape spaces

14h45-15h15: A. Weinmann (U. Keiserslautern)
Variational denoising for manifold-valued data.

15h15-15h45: M. Guillaud (Huawei Technologies Co. Ltd.)
Interference Alignment via Message-Passing.

15h45-16h15: Pause

16h15-17h00: Y. Ollivier (Univ. Paris Sud Orsay)
Information-geometric optimization: The interest of invariance principles for discrete and continuous optimization 

Résumés des contributions

P.-A. Absil (UC Louvain)
Optimization and curve fitting on manifolds.

After a (not so) brief overview of the area of optimization on manifolds, I will discuss curve-fitting and interpolation problems on manifolds. Manifolds of interest include the rotation group SO(3) (generation of rigid body motions from sample points), the set of 3x3 symmetric positive-definite matrices (interpolation of diffusion tensors) and the shape manifold (morphing).
The general problem can be formulated as follows. Given data points p_0,...,p_N on a Riemannian manifold M, as well as time instants t_0<t_1<...<t_N, find a curve on M that "best" approximates the data points at the given instants while  being as "regular" as possible. More specifically, we seek the curve that minimizes anenergy function E defined as a weighted sum of (i) a sum-of-squares term penalizing the lack of fitting to the data points at the given times and (ii) a regularity term defined as the mean squared acceleration of the curve. The Euler-Lagrange necessary conditions for this problem are known to take the form of a fourth-order ordinary differential equation involving the curvature tensor of M, which is in general hard to solve. Instead, we simplify the problem by restricting the set of admissible curves and by resorting to suboptimal Riemannian generalizations of Euclidean techniques.

N. Boumal (ENS Ulm)
Manopt, a Matlab toolbox for optimization on manifolds

As a follow up to Pierre-Antoine Absil's talk on Riemannian optimization in general, I will present a toolbox called Manopt.  This toolbox aims to make state of the art algorithms in Riemannian optimization easy to use. It comes with a collection of solvers (algorithms) as well as a collection of geometries, so that it is straightforward to tackle optimization problems with rank constraints, orthogonality constraints, certain symmetries, etc.
The toolbox is open source, well documented and is available at http://www.manopt.org. The website features a forum where users are welcome to post questions, related to the toolbox as well as to Riemannian optimization in general. 

S. Bonnabel (Mines ParisTech)
Méthodes de gradient stochastique sur les variétés riemanniennes.

Le gradient stochastique est une méthode d'optimisation simple pour trouver le minimum d'une fonction dont les évaluations sont corrompues par un bruit de mesure. La méthode est étudiée depuis plusieurs décennies, mais sa simplicité a engendré une recrudescence d'intérêt récente pour des problèmes d'apprentissage statistique de grande taille. Dans cet exposé, nous exposerons d'abord la méthode conventionnelle, puis nous l'étendrons au cas où la fonction à minimiser est définie sur une variété riemannienne. L'algorithme conserve alors certaines propriétés de convergence, et trouve diverses applications, à savoir: Analyse par Composante Principale en ligne (variété de Stiefel), moyennes (filtrage) de matrices semi-définies positives, apprentissage de matrice semi-positive de rang faible (ou distance de Mahalanobis de rang faible), et estimation décentralisée de matrice de covariance (cône des matrices définies positives). 

M. Bacak (Telecom ParisTech)
Proximal point algorithm in Hadamard spaces.

Hadamard spaces are geodesic metric spaces of nonpositive curvature and play crucial roles in geometry and geometric group theory. They have also become increasingly important in various applications including computational phylogenetics, medical imaging and robotics. Since one often solves an optimization problem in such applications, it is natural to ask which tools we have at our disposal. It turns out that many optimization algorithms, which are known from linear spaces, work equally well in Hadamard spaces. In this talk we show that the proximal point algorithm is well defined and converges. As an application, it enables us to compute medians and means of phylogenetic trees.

P.-Y. Gousenbourger (UC Louvain)
Interpolation on Riemannian manifolds with a C1 piecewise-Bézier curves.

More and more, manifolds (i.e. smooth spaces) are used to solve problems that would have been very time and ressources consuming if they were defined on the classical Euclidean space (because of non-linear constraints restricting the solutions to a certain subspace). In that purpose, interpolation [MSL04, PN07] and optimization [AMS08, BMAS14] tools are developed in several fields like big data mining [Bou14], image modeling and processing [Pey09] or invariant pattern recognition methods. We focus on interpolation. In this work [GSA14], we propose a new framework to fit a smooth path to a set of n+1 data points on a Riemannian manifold. This path is composed of Bézier functions. Specifically, we seek a C1 piecewise-Bézier interpolation curve for the data (p0, . . . , pn), such that the segment joining p0 and p1, as well as the segment joining pn−1 and pn, are Bézier curves of order two (i.e., with one intermediate control point), while all the other segments are Bézier curves of order three (i.e., with two intermediate control points). In view of the endpoint velocity formula [PN07, (6)], fixing the curve velocity vector at each intermediate interpolation point
fully determines all the control points, and thus the curve. The task therefore reduces to choosing those velocities. The velocity directions are chosen in an arbitrary way ; The optimal velocity magnitudes are solutions, in the Euclidean case, of a certain tridiagonal system of equations obtained by minimizing the mean squared acceleration of the curve. We generalize this linear system to Riemannian manifolds and use it to set the velocity magnitudes at the intermediate interpolation points. Even though the velocity directions are still suboptimal in general and the velocity magnitudes are suboptimal on nonlinear manifolds, the numerical experiments indicate that the method produces good-looking curves on several manifolds and for a wide range of data point positions.
The advantage of this method is that it is general on various Riemannian manifolds if only three objects of differential geometry are known on the manifold : the exponential and logarithmic maps and the inner scalar product. This method is generally neither time nor space consuming, and brings good quality visual results on the Euclidean space, the hypersphere, the "shape manifold" and the special orthogonal group SO(3).

A. Trouvé (ENS Cachan)
Geodesic shooting in shape spaces.

Shape spaces as infinite dimensional riemannian manifolds, are challenging both mathematicians and computer scientists. We will discuss in this talk the question of the existence and computation of the geodesic shooting that arises in several important optimisation problems.

A. Weinmann (U. Keiserslautern)
Variational denoising for manifold-valued data.

Nonlinear data spaces appear in various branches of applied mathematics and in particular in image processing. Examples are nonlinear color spaces, the motion group or the Riemannian manifold of positive (covariance) matrices appearing, e.g., in diffusion tensor imaging. In this talk we consider TV type functionals for manifold-valued data. We present algorithms and show applications to denoising. Furthermore, we present a second order approach for cyclic data. We conclude with a look at Potts and Mumford-Shah type functionals.

M. Guillaud (Huawei Technologies Co. Ltd.), M. Zezaee, G. Matz
Interference Alignment via Message-Passing.

We introduce an iterative solution to the problem of interference alignment (IA) over MIMO channels based on a message-passing formulation. We propose a parameterization of the messages that enables the computation of IA precoders by a min-sum algorithm over continuous variable spaces -- under this parameterization, suitable approximations of the messages can be computed in closed-form. We show that the iterative leakage minimization algorithm of Cadambe et al. is a special case of our message-passing algorithm, obtained for a particular schedule. Finally, we show that the proposed algorithm compares favorably to iterative leakage minimization in terms of convergence speed, and discuss a distributed implementation.

Y. Ollivier (Univ. Paris Sud Orsay)
Information-geometric optimization: The interest of invariance principles for discrete and continuous optimization 

Black box optimization is the problem of searching for the minimum of a function on a given space (discrete or continuous), without any prior knowledge about the function. Information geometry provides a systematic method, IGO (information-geometric optimization) to easily build optimization algorithms having nice invariance properties; in  particular it minimizes the influence of arbitrary choices such as how the space of solutions is represented. In some situations IGO recovers known and widely used algorithms, thus providing theoretical justification for them. Specific properties of information geometry and the Kullback-Leibler divergence guarantee, at each step, minimal diversity loss in the exploration of possible solutions; this suggests IGO algorithms automatically tune the simultaneous exploration of different regions. 

F. Barbaresco (Thales Air Systems, Département Concepts Radar Avancés)
Espaces métriques de Fisher/Koszul/Souriau et optimisation par maximum d’entropie: géométrie hessienne de Koszul et thermodynamique des groupes de Lie de Souriau

Classiquement, il est possible d'introduire une métrique pour les matrices structurées de covariance dans le cadre de la géométrie de l'information, en considérant ces matrices comme des paramètres d'une densité de probabilité. La géométrie de l'information est en fait un cas particulier d'une théorie plus générale introduite par le mathématicien Jean-Louis Koszul dans le cadre des géométries hessiennes. Dans la géométrie de Koszul, la métrique est introduite comme le hessien du logarithme de la fonction caractéristique généralisée associée aux cône convexe pour ces matrices via le produit intérieur de Cartan-Killing. De façon duale grâce à la transformée de Legendre, une métrique peut être obtenue dans un système de coordonnées duales comme le hessien de l'entropie généralisée (entropie de Shannon). Il est ensuite possible de définir une densité de probabilité sur ces variétés de matrices comme solution du Maximum d'Entropie. De cette densité, il est alors possible de calculer des p-moyennes sur ces variétes de matrices (p=1 barycentre médian, p=2 barycentre moyen). Ce procédé a été généralisé en physique statistique par le physicien Jean-Marie Souriau en considérant l'action d'un groupe de Lie sur une variété symplectique. Souriau a montré que la métrique précédente pouvait être définie comme une « capacité thermique généralisée » dans le cadre d'une « thermodynamique des groupes de Lie ». Dans cette nouvelle thermodynamique, l'équilibre de Gibbs peut être rendu covariant lorsque le système physique est soumis à une dynamique liée au groupe de Galilée ou au groupe de Poincaré, grâce à une température (de planck) « géométrique » vectorielle qui appartient à l'algèbre de Lie du groupe dynamique. L'approche permet de géométriser le théorème de Noether en calcul des variations. Nous illustrerons ces outils pour les variétés des matrices de covariance de signaux stationnaires de structure de type Toeplitz Hermitienne définie positive pour les séries temporelles, et de structure Toeplitz-Block-Toeplitz Hermitienne définie positive pour les séries spatio-temporelles. Nous montrerons des résultats dans le domaine du traitement Doppler ou spatio-temporel de signaux radar.

1. Koszul J.L., Variétés localement plates et convexité, Osaka J. Math. , n°2, p.285-290, 1965

2. Koszul J.L., Domaines bornées homogènes et orbites de groupes de transformations affines, Bull. Soc. Math. France 89, pp. 515-533., 1961

3. Koszul J.L., Ouverts convexes homogènes des espaces affines, Math. Z. 79, pp. 254-259., 1962

4. Koszul J.L., Déformations des variétés localement plates, .Ann Inst Fourier, 18 , 103-114., 1968

5. Souriau J.M., Définition covariante des équilibres thermodynamiques, Suppl. Nuov. Cimento, n°1, pp. 203–216, 1966

6. Souriau J.M., Structure of dynamical systems, volume 149 of Progress in Mathematics. Birkhäuser Boston Inc., Boston, MA, 1997. A symplectic view of physics

7. Souriau J.M., Thermodynamique et géométrie. In Differential geometrical methods in mathematical physics, II, vol. 676 of Lecture Notes in Math., pages 369-397. Springer, Berlin, 1978

8. Souriau J.M., Géométrie Symplectique et physique mathématique, CNRS 75/P.785, Dec. 1975

9. Souriau J.M., Mécanique classique et géométrie symplectique, CNRS CPT-84/PE-1695, Nov. 1984

10. Shima H., The Geometry of Hessian Structures, World Scientific, 2007

11. Barbaresco F., Eidetic Reduction of Information Geometry through Legendre Duality of Koszul Characteristic Function and Entropy, Geometric Theory of Information, Springer, 2014

12. Barbaresco F., Koszul Information Geometry and Souriau Geometric Temperature/Capacity of Lie Group Thermodynamics, MDPI Entropy, n°16, 2014.