Search

Your search keyword '"CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)"' showing total 3,061 results
Start Over Author "CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)"
3,061 results on '"CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)"'

1. A $\Gamma$-Convergence Result for the Upper Bound Limit Analysis of Plates

Author

Multi-échelle ; Laboratoire Navier (NAVIER UMR 8205) ; Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR) - École des Ponts ParisTech (ENPC) - CNRS - Université Paris Est (UPE) - Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR) - École des Ponts ParisTech (ENPC) - CNRS - Université Paris Est (UPE), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE) ; CNRS - Université Paris IX - Paris Dauphine, MOKAPLAN (INRIA Paris-Rocquencourt) ; INRIA, European Project : 279593, ERC, ERC-2011-StG_20101014, SIGMA-VISION(2011), Bleyer, Jérémy, Carlier, Guillaume, Duval, Vincent, Mirebeau, Jean-Marie, Peyré, Gabriel, Multi-échelle ; Laboratoire Navier (NAVIER UMR 8205) ; Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR) - École des Ponts ParisTech (ENPC) - CNRS - Université Paris Est (UPE) - Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR) - École des Ponts ParisTech (ENPC) - CNRS - Université Paris Est (UPE), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE) ; CNRS - Université Paris IX - Paris Dauphine, MOKAPLAN (INRIA Paris-Rocquencourt) ; INRIA, European Project : 279593, ERC, ERC-2011-StG_20101014, SIGMA-VISION(2011), Bleyer, Jérémy, Carlier, Guillaume, Duval, Vincent, Mirebeau, Jean-Marie, and Peyré, Gabriel

Abstract

Upper bound limit analysis allows one to evaluate directly the ultimate load of structures without performing a cumbersome incremental analysis. In order to numerically apply this method to thin plates in bending, several authors have proposed to use various finite elements discretizations. We provide in this paper a mathematical analysis which ensures the convergence of the finite element method, even with finite elements with discontinuous derivatives such as the quadratic 6 node Lagrange triangles and the cubic Hermite triangles. More precisely, we prove the $\Gamma$-convergence of the discretized problems towards the continuous limit analysis problem. Numerical results illustrate the relevance of this analysis for the yield design of both homogeneous and non-homogeneous materials., L'analyse limite permet d'évaluer directement la charge maximale supportée par une structure mécanique sans avoir à effectuer une analyse incrémentale lourde. Afin d'appliquer cette méthode à l'étude des plaques minces en flexion, certains auteurs ont proposé d'utiliser diverses discrétisations par éléments finis. Dans cet article, nous étudions mathématiquement la convergence de la méthode des éléments finis pour ce problème, y compris avec des interpolées à dérivées discontinues comme les éléments de Lagrange quadratiques ou ceux de Hermite cubiques. Plus précisément nous montrons la $\Gamma$-convergence des problèmes discrétisés vers le problème continu d'analyse limite. Des expériences numériques illustrent la pertinence de cette analyse pour le calcul à la rupture de matériaux homogènes et non homogènes.

2. Mass concentration in rescaled first order integral functionals

Author

Monteil, Antonin, Pegon, Paul, Laboratoire Analyse et Mathématiques Appliquées (LAMA), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), A. M. acknowledges support by Leverhulme grant RPG-2018-438., Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), and Pegon, Paul

Subjects
Relaxation, H-mass, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], semicontinuity, [MATH] Mathematics [math], convergence of measures, Functionals on measures, Mathematics - Analysis of PDEs, integral functionals, branched transport, Primary: 28A33, 49J45, 46E35, Secondary: 49Q20, 76T99, 49Q22, 49J10, Γ-convergence, Optimization and Control (math.OC), FOS: Mathematics, concentration-compactness, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AP] Mathematics [math]/Analysis of PDEs [math.AP], [MATH]Mathematics [math], Mathematics - Optimization and Control, Cahn-Hilliard fluids, Analysis of PDEs (math.AP), Calculus of variations
Abstract

We consider first order local minimization problems of the form $\min \int_{\mathbb{R}^N}f(u,\nabla u)$ under a mass constraint $\int_{\mathbb{R}^N}u=m\in\mathbb{R}$. We prove that the minimal energy function $H(m)$ is always concave on $(-\infty,0)$ and $(0,+\infty)$, and that relevant rescalings of the energy, depending on a small parameter $\varepsilon$, $\Gamma$-converge in the weak topology of measures towards the $H$-mass, defined for atomic measures $\sum_i m_i\delta_{x_i}$ as $\sum_i H(m_i)$. We also consider space dependent Lagrangians $f(x,u,\nabla u)$, which cover the case of space dependent $H$-masses $\sum_i H(x_i,m_i)$, and also the case of a family of Lagrangians $(f_\varepsilon)_\varepsilon$ converging as $\varepsilon\to 0$. The $\Gamma$-convergence result holds under mild assumptions on $f$, and covers several situations including homogeneous \(H\)-masses in any dimension $N\geq 2$ for exponents above a critical threshold, and all concave $H$-masses in dimension $N=1$. Our result yields in particular the concentration of Cahn-Hilliard fluids into droplets, and is related to the approximation of branched transport by elliptic energies.

Published
2022

3. Stability of optimal traffic plans in the irrigation problem

Author

Antoine Prouff, Antonio De Rosa, Andrea Marchese, Maria Colombo, Paul Pegon, Ecole Polytechnique Fédérale de Lausanne (EPFL), Courant Institute of Mathematical Sciences [New York] (CIMS), New York University [New York] (NYU), NYU System (NYU)-NYU System (NYU), Department of mathematics/Dipartimento di Matematica [Univ. Trento], Università degli Studi di Trento (UNITN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Maria Colombo was partially supported by the Swiss National Science Foundation grant 200021_182565. Antonio De Rosa has been supported by the NSF DMS Grant No. 1906451. Andrea Marchese acknowledges partial support from GNAMPA-INdAM., Department of Mathematics [College Park], University of Maryland [College Park], University of Maryland System-University of Maryland System, Bocconi Institute for Data Science and Analytics (BIDSA), Bocconi University [Milan, Italy], Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, M. C. was partially supported by the Swiss National Science Foundation grant 200021_182565. A. D. R. has been supported by the NSF DMS Grant No. 1906451 and the NSF DMS Grant No. 2112311. A. M. acknowledges partial support from GNAMPA-INdAM. A.P. was supported by the Fondation Mathématiques Jacques Hadamard. P.P and A.P. both acknowledge EPFL for hosting them during the semester this paper was prepared., Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)

Subjects
BRANCHED TRANSPORT, Mathematical optimization, Irrigation, TRAFFIC PLANS, [MATH.MATH-CA]Mathematics [math]/Classical Analysis and ODEs [math.CA], 01 natural sciences, Stability (probability), symbols.namesake, Mathematics - Analysis of PDEs, Classical Analysis and ODEs (math.CA), FOS: Mathematics, Computer Science::Networking and Internet Architecture, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Discrete Mathematics and Combinatorics, Limit (mathematics), 0101 mathematics, Mathematics - Optimization and Control, Mathematics, TRANSPORTATION NETWORK, BRANCHED TRANSPORT, IRRIGATION PROBLEM, TRAFFIC PLANS, STABILITY, STABILITY, IRRIGATION PROBLEM, Applied Mathematics, TRANSPORTATION NETWORK, 010102 general mathematics, Eulerian path, Flow network, 010101 applied mathematics, Optimization and Control (math.OC), Mathematics - Classical Analysis and ODEs, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Analysis, Lagrangian, Analysis of PDEs (math.AP)
Abstract

We prove the stability of optimal traffic plans in branched transport. In particular, we show that any limit of optimal traffic plans is optimal as well. This result goes beyond the Eulerian stability proved in [7], extending it to the Lagrangian framework.

Published
2022

4. Convex geometry of finite exchangeable laws and de Finetti style representation with universal correlated corrections

Author

Guillaume Carlier, Gero Friesecke, Daniela Vögler, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Zentrum Mathematik [Munchen] (TUM), Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Technische Universität München [München] (TUM)

Subjects
Statistics and Probability, Hewitt-Savage theorem, 60G09, 52-XX, 90C06, Probability (math.PR), Multi-marginal optimal transport, Bayesian statistics, Finite exchangeability, Optimization and Control (math.OC), N-representability, de Finetti, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Statistics, Probability and Uncertainty, Choquet theory, Mathematics - Optimization and Control, Extremal measures, Analysis, Mathematics - Probability
Abstract

We present a novel analogue for finite exchangeable sequences of the de Finetti, Hewitt and Savage theorem and investigate its implications for multi-marginal optimal transport (MMOT) and Bayesian statistics. If $(Z_1,...,Z_N)$ is a finitely exchangeable sequence of $N$ random variables taking values in some Polish space $X$, we show that the law $\mu_k$ of the first $k$ components has a representation of the form $\mu_k=\int_{{\mathcal P}_{\frac{1}{N}}(X)} F_{N,k}(\lambda) \, \mbox{d} \alpha(\lambda)$ for some probability measure $\alpha$ on the set of $1/N$-quantized probability measures on $X$ and certain universal polynomials $F_{N,k}$. The latter consist of a leading term $N^{k-1}\! /{\small \prod_{j=1}^{k-1}(N\! -\! j)\, \lambda^{\otimes k}}$ and a finite, exponentially decaying series of correlated corrections of order $N^{-j}$ ($j=1,...,k$). The $F_{N,k}(\lambda)$ are precisely the extremal such laws, expressed via an explicit polynomial formula in terms of their one-point marginals $\lambda$. Applications include novel approximations of MMOT via polynomial convexification and the identification of the remainder which is estimated in the celebrated error bound of Diaconis-Freedman between finite and infinite exchangeable laws.

Published
2021

5. SISTA: learning optimal transport costs under sparsity constraints

Author

Guillaume Carlier, Arnaud Dupuy, Alfred Galichon, Yifei Sun, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Luxembourg [Luxembourg], Courant Institute of Mathematical Sciences [New York] (CIMS), New York University [New York] (NYU), NYU System (NYU)-NYU System (NYU), NYU System (NYU), Département d'économie (Sciences Po) (ECON), Sciences Po (Sciences Po)-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)

Subjects
FOS: Computer and information sciences, Coordinate descent, 050208 finance, 05 social sciences, Inverse optimal transport, Methodology (stat.ME), Optimization and Control (math.OC), ISTA, 0502 economics and business, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 050207 economics, Mathematics - Optimization and Control, Statistics - Methodology
Abstract

In this paper, we describe a novel iterative procedure called SISTA to learn the underlying cost in optimal transport problems. SISTA is a hybrid between two classical methods, coordinate descent ("S"-inkhorn) and proximal gradient descent ("ISTA"). It alternates between a phase of exact minimization over the transport potentials and a phase of proximal gradient descent over the parameters of the transport cost. We prove that this method converges linearly, and we illustrate on simulated examples that it is significantly faster than both coordinate descent and ISTA. We apply it to estimating a model of migration, which predicts the flow of migrants using country-specific characteristics and pairwise measures of dissimilarity between countries. This application demonstrates the effectiveness of machine learning in quantitative social sciences.

Published
2021

6. Dynamical Programming for off-the-grid dynamic Inverse Problems

Author

Duval, Vincent, Tovey, Robert, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), ANR-19-CE48-0017,CIPRESSI,Traitement d'images continues: modèles et algorithmes(2019), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
Optimization and Control (math.OC), FOS: Mathematics, Numerical Analysis (math.NA), Mathematics - Numerical Analysis, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], Mathematics - Optimization and Control
Abstract

In this work we consider algorithms for reconstructing time-varying data into a finite sum of discrete trajectories, alternatively, an off-the-grid sparse-spikes decomposition which is continuous in time. Recent work showed that this decomposition was possible by minimising a convex variational model which combined a quadratic data fidelity with dynamical Optimal Transport. We generalise this framework and propose new numerical methods which leverage efficient classical algorithms for computing shortest paths on directed acyclic graphs. Our theoretical analysis confirms that these methods converge to globally optimal reconstructions which represent a finite number of discrete trajectories. Numerically, we show new examples for unbalanced Optimal Transport penalties, and for balanced examples we are 100 times faster in comparison to the previously known method.; Dans cet article, nous considérons des algorithmes de reconstruction sans grille pour des mesures parcimonieuses à partir de données dynamiques. En particulier, le signal reconstruit est une somme finie de mesures de Dirac dont les positions et les amplitudes varient continûment. Des travaux récents ont montré qu'une telle décomposition était possible dans un cadre variationnel convexe qui combine une attache aux données quadratique avec la formulation dynamique du transport optimal. Nous généralisons ce cadre et proposons une nouvelle méthode numérique qui exploite des algorithmes efficaces classiques de plus court chemin sur des graphes acycliques orientés. Notre analyse théorique confirme que ces méthodes convergent vers des minimiseurs globaux. Nous illustrons ces méthodes sur des exemples nouveaux impliquant le transport optimal non-équilibré, et, pour le transport classique, notre méthode est près de 100 fois plus rapide que l'état de l'art.

Published
2021

7. Entropic Unbalanced Optimal Transport: Application to Full-Waveform Inversion and Numerical Illustration

Author

Yu, Miao, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Paris, Jean-Pierre Vilotte, Jean-David Benamou, Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Inversion de formes d’onde, Transport-optimal entropique non-équilibré, [SDU]Sciences of the Universe [physics], Unbalanced entropic optimal transport, Sinkhorn divergence, Full-waveform inversion, Divergence de Sinkhorn, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

Seismic tomography aims at inferring physical properties and reconstructing quantitatively the “model”, i.e. structures of the Earth interior, from the mechanical waves – radiated by natural and man-made seismic sources – that are recorded at the surface by receivers in the form of seis-mograms. Over the past decades, Full-Waveform inversion (FWI) has been actively developed in both academia and industry, and has proven to be a powerful tool that dramatically improved the capability to estimate physical properties and structures of various geological targets from global to local scales.Full-waveform inversion (FWI) is formulated as a nonlinear, PDE-based optimisation problem that is classically solved by iterative minimisation of an objective function – measuring the misÿt bet-ween synthetic and observed seismic waveforms – using adjoint-based solution methods. Adjoint-based solution methods allow the computation of the derivative of the objective function with respect to the model parameters by combining the synthetic forward waveÿeld and an adjoint waveÿeld governed by a set of adjoint equations and adjoint subsidiary conditions.In practice, however, solving FWI problems using local, nonlinear optimisation methods is facing challenges that preclude routine use. The quality of the inversion, simultaneously dealing with long and short wavelengths information, is degraded by the lack of low frequencies and also depends on a good starting model. These limitations are linked to the ill-posed nature of the inverse problem which can be easily trapped into a local minimum.One proposed research direction to reduce the dependency on the initial model, is to replace the classical least-squares based misÿt by other objective functions – possibly involving nonlinear transformation of the seismic signal –hence promoting the convexity and trying to enlarge the basin of attraction of the global minimum.Optimal Transport (OT) theory has recently been use in inverse problems and machine learning. Optimal Transport lifts the properties of the squared Euclidean distance to the space of probability distributions. The optimal value (squared) of the transport itself deÿnes a distance called the 2-Wasserstein distance. This quantity is again convex but now on the set of probability distributions.This trend is already active for FWI, this thesis is part of it. The OT approach is still largely open on three fronts : Seismic Waveforms are not probability distributions, lacking positivity and nor-malised total mass. Convexity with respect to the model is not guaranteed and ÿnally the actual computation of the OT distance is not cheap.In this work we use and combine – from an academic point of view – two recent extensions of OT in the context of FWI. First the “unbalanced” OT distance, which rigorously deÿnes a distance on the set of positive Radon measure thus by-passing the data normalisation issue (but not the positivity problem). Then, the entropic regularisation OT framework and in particular the simple and easy to compute variant called Sinkhorn divergence providing a good approximation of the 2-Wasserstein distance. The Sinkhorn divergence can be naturally extended to unbalanced OT.We use these tools to construct and implement our unbalanced OT misÿt and discuss its use in the context of full-waveform inversion through a number of academic examples and classical benchmark problems.; Les méthodes de tomographie sismique visent à inférer les propriétés physique et reconstruire le “modèle”, i.e. les structures de l’intérieur de la Terre, à partir des ondes mécaniques - radiées par des sources naturelles ou anthropogéniques - enregistrées par des récepteurs en surface sous la forme de sismogrammes. Les méthodes d’inversion de formes d’onde ont été activement déve-loppées dans les contextes académiques et industriels et sont devenus des outils puissants pour améliorer l’estimation des propriétés physiques et des structures d’objets géologiques depuis les échelles globales jusqu’aux échelles locales de la géophysique d’exploration.L’inversion de formes d’onde est formulée comme un problème d’optimisation non linéaire, as-socié à un système d’équations aux dérivées partielles. Il est classiquement résolu par des mé-thodes d’optimisation locale via la minimisation itérative d’une fonction coût qui mesure la di˙é-rence entre les sismogrammes observés et synthétiques, et utilisent des méthodes d’état adjoint. Les méthodes d’état adjoint permettent le calcul des dérivées de la fonction coût par rapport aux paramètres du modèle en combinant le champ d’onde direct et un champ d’onde adjoint gou-verné par un système d’équations adjointes et des conditions adjointes complémentaires.Les méthodes d’inversion de forme d’onde, qui inversent simultanément les courtes et grandes longueurs d’onde, sou˙rent malheureusement en pratique de di°cultés qui restreignent leur uti-lisation pratique. Leurs capacités se détériorent du fait du déÿcit en basse fréquence des obser-vations et d’un bon modèle initial. Des limitations qui sont associées à la nature mal posée du problème inverse qui peut facilement être piégé dans un minimum local.Une direction proposée, aÿn de réduire la dépendance vis à vis du modèle initial, est de rem-placer la fonction classique, basée sur une distance de type moindres carrés, par de nouvelles fonctions coûts, pouvant impliquer une transformation non linéaire du signal, aÿn de promouvoir la convexité et élargir le bassin d’attraction du minimum global.La théorie du Transport Optimal (OT) a récemment été utilisée dans le cadre des problèmes in-verses et de l’apprentissage automatique. Le transport optimal généralise les propriétés de la distance euclidienne au carré à l’espace des distributions de probabilité. La valeur optimale (au carré) du transport lui-même déÿnit une distance appelée distance 2-Wasserstein. Cette quantité est à nouveau convexe mais maintenant sur l’ensemble des distributions de probabilité.Le Transport Optimal est déjà utilisé en FWI, cette thèse en fait partie. L’approche OT est encore largement ouverte sur trois fronts : les formes d’onde sismiques ne sont ni positives ni de masse totale normalisée. La convexité par rapport au modèle n’est pas garantie et ÿnalement le calcul réel de la distance OT est coûteuse.Dans ce travail, nous utilisons et combinons - d’un point de vue académique - deux extensions ré-centes d’OT dans le contexte FWI. D’abord la distance OT “non-équilibrée”, qui déÿnit rigoureuse-ment une distance sur l’ensemble des mesures de Radon positives contournant ainsi le problème de normalisation des données (mais pas le problème de positivité). Puis le cadre du Transport Optimal entropique et en particulier la variante simple et facile à calculer appelée divergence de Sinkhorn fournissant une bonne approximation de la distance 2-Wasserstein. La divergence de Sinkhorn peut être naturellement étendue au transport “non-équilibré”.Nous utilisons ces outils pour construire et mettre en œuvre une fonction coût OT “non-équilibrée”. Nous discutons de son utilisation dans le contexte FWI au travers d’un certain nombre d’exemples académiques et de problèmes de référence classiques.

Published
2021

8. A spatial Pareto exchange economy problem

Author

X. Bacon, G. Carlier, B. Nazaret, Statistique, Analyse et Modélisation Multidisciplinaire (SAmos-Marin Mersenne) (SAMM), Université Paris 1 Panthéon-Sorbonne (UP1), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, GC is grateful to the Agence Nationale de la Recherche for its support through the projects MAGA (ANR-16-CE40-0014) and MFG(ANR-16-CE40-0015-01)., ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016), ANR-16-CE40-0015,MFG,Jeux Champs Moyen(2016), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
TheoryofComputation_MISCELLANEOUS, Sinkhorn algorithm, Control and Optimization, Convex duality, Exchange economy Pareto optimality, Applied Mathematics, MESH: MS Classification: 49Q22, 91B72, Second welfare theorem, Optimal transport, TheoryofComputation_GENERAL, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Entropic optimal transport
Abstract

We use convex duality techniques to study a spatial Pareto problem with transport costs and derive a spatial second welfare theorem. The existence of an integrable equilibrium distribution of quantities is nontrivial and established under general monotonicity assumptions. Our variational approach also enables us to give a numerical algorithmà la Sinkhorn and present simulations for equilibrium prices and quantities in one-dimensional domains and a network of French cities.

Published
2021

9. Finite volume approximation of optimal transport and Wasserstein gradient flows

Author

Todeschi, Gabriele, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), PSL Université Paris Dauphine, Jean-David Benamou, Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Université Paris sciences et lettres, Clément Cancès, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Wasserstein gradient flows, Optimization, Volumes finis, Transport optimal, Finite volumes, Optimal transport, Optimisation, [MATH]Mathematics [math], [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], Flots de gradient Wasserstein
Abstract

This thesis is devoted to the design of locally conservative and structure preserving schemes for Wasserstein gradient flows, i.e. steepest descent curves in the Wasserstein space. The time discretization is based on variational approaches that mimic at the discrete in time level the behavior of steepest descent curves. These discretizations involve the computation of the Wasserstein distance, an instance of optimal transport problem. The space discretization is based on Two-Point Flux Approximation (TPFA) finite volumes, a well-known methodology particularly suited for the discretization of partial differential equations that present a conservative structure. In order to preserve the variational structure at the discrete level, we follow a first discretize then optimize approach. We start by presenting TPFA discretizations for the Wasserstein distance based on the Benamou-Brenier dynamical formulation. We expose some stability issues related to these discetizations, propose a possible solution to overcome them and derive quantitative estimate on the convergence of the discrete model. To solve the discrete optimization problem, we introduce an interior point strategy. Then, we propose first and second order accurate schemes for Wasserstein gradient flows. At this level, to reduce the computational complexity, we use an implicit linearization of the Wasserstein distance. By taking adavantage of the monotonicity of the upwind reconstruction, we propose a first order scheme which can be efficiently solved with a Newton method and show its convergence towards distributional solutions of the Fokker-Planck equation. In order to higher the accuracy in space, we use a centered reconstruction, which requires a different optimization technique. We use again the interior point strategy for this purpose. Finally, we propose a modified variational BDF2 time discretization and prove its convergence towards Wasserstein gradient flows. Thanks to these new discretizations, we design a second order accurate scheme in both time and space. All our approaches are validated with several numerical results.; Cette thèse a pour objet la construction de schémas numériques localement conservatif et préservant la structure pour des flots de gradient Wasserstein, c’est à dire des courbes de descente maximale dans l’espace de Wasserstein. Les discrétisations en temps reposent sur des formulations variationnelles imitant au niveau discret ce comportement de courbes de descente maximale. Ces discrétisation font intervenir le calcul de la distance de Wasserstein, un exemple de problèmes de transport optimal. Les discrétisations en espaces sont basées sur des approximations volumes finis avec reconstructions à deux points des flux, également appelés schémas TPFA. Ces méthodes sont bien connues et particulièrement adaptées pour discrétiser des équations conservatives. Afin de conserver les structures variationnelles au niveau discret, notre approche est de d’abord discrétiser puis optimiser. Dans une première partie nous présentons des discrétisations TPFA pour la distance de Wasserstein, basées sur la formulation dynamique de Benamou-Brenier du transport optimal. Nous montrons des problèmes de stabilité liés à ces discrétisations et proposons une méthode permettant de les surmonter. Nous dérivons des estimations quantitatives de convergence pour ce model discret. Afin de résoudre le problème d'optimisation discret, nous introduisons une stratégie de point intérieur. Ensuite nous proposons des schémas d’ordre un puis deux pour des flots de gradients Wasserstein. Afin de réduire la complexité numérique des problèmes étudiés nous utilisons une linéarisation implicite de la distance de Wasserstein. En exploitant la monotonie de la reconstruction upwind, nous proposons un schéma d'ordre un que l'on peut résoudre efficacement avec une méthode de Newton et nous montrons sa convergence vers des solutions faibles de l'équation de Fokker-Planck. Pour augmenter l’ordre de convergence en espace, nous utilisons une reconstruction centrée qui nécessite une technique d’optimisation différente. Nous utilisons à nouveau la stratégie du point intérieur pour cela. Finalement, pour monter en ordre en temps, nous proposons une version modifiée de la discrétisation variationnelle BDF2 pour laquelle nous prouvons la convergence vers des flots de gradient Wasserstein. À l'aide de ces nouvelles discrétisations, nous construisons un schéma d'ordre deux en espace et en temps. Tous les schémas proposés sont accompagnés de nombreux résultats numériques.

Published
2021

10. A FreeForm Optics Application of Entropic Optimal Transport

Author

Rukhaia, Giorgi, Benamou, Jean-David, Ijzerman, Wilbert, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres, Jean-David Benamou, Wilbert IJzerman, European Project: 765374,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions / H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,ROMSOC(2017), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, PSL Université Paris Dauphine, INRIA Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Non-Linear optimization, Problème inverse du reflecteur, Optimisation non linéaire, Optimisation non linèaire, Non-linear opti- mization, Transport Optimal entropique, Inverse Reflector Problem, Algorithme de Sinkhorn, Sinkhorn algorithm, [MATH.MATH-MP]Mathematics [math]/Mathematical Physics [math-ph], Entropic Optimal Transport, Extended source, Problème inverse du réflecteur, [MATH]Mathematics [math], Source lumineuse étendue
Abstract

In this work, we address the “freeform optics” inverse problem of designing a reflector surface mapping a prescribed source distribution of light to a prescribed target far-field distribution, for the point light source and the extended light source. When the source is a point source, the light distribution has support only on the optics ray directions. In this setting, the inverse problem is well-posed for arbitrary source and target probability distributions. It can be recast as an optimal transport problem and is a classic example of an optimal transport problem with a non-euclidean displacement cost. We explore the use of entropic Optimal Transport and the associated Sinkhorn algorithm to solve it numerically. As the reflector modeling is based on the Kantorovich potentials, several questions arise. First, on the convergence of the discrete entropic approximation and here we follow the recent work of Berman and in particular the imposed discretization requirements therein. Secondly, the correction of the bias induced by the entropic Optimal Transport using the recent notion of Sinkhorn divergences is shown to be necessary to achieve satisfactory results. For the point source problem, we discuss the necessary mathematical and numerical tools needed to produce and analyze the obtained numerical results. We find that Sinkhorn algorithm may be adapted to the resolution of the point source to far-field reflector problem.We are not aware of any similar mathematical formulation in the extended source case: i.e. the source has an “étendue” with support in the product space: physical domain-ray directions. We propose to leverage the well-posed variational formulation of the point source problem to build a smooth parameterization of the reflector and the map modeling the reflection. Under this parametrization, we can construct a smooth cost function to optimize for the best solution in this class of reflectors. Both steps, the parameterization and the cost function, are related to entropic optimal transport distances. We also take advantage of recent progress in the optimization techniques and the efficient implementations of Sinkhorn algorithm to perform a numerical study.; Dans ce travail, nous abordons un problème inverse en optique anidolique consistant à déterminer une surface capable de réflechir une distribution de lumière source à une distribution cible en champ lointain, toutes deux prescrites. La source lumineuse peut être ponctuelle ou étendue. Lorsque la source est une source ponctuelle , la distribution est supportée uniquement sur les directions des rayons optiques. Dans ce contexte, le problème inverse est bien posé pour des distributions de probabilité source et cible arbitraires. Il peut être reformulé comme un problème de transport optimal et constitue un exemple célébre de transport optimal sous un coût de déplacement non euclidien. Nous explorons l’utilisation du transport optimal entropique et de l’algorithme Sinkhorn associé pour le résoudre numériquement. La modélisation du réflecteur étant basée sur les potentiels de Kantorovich, plusieurs questions se posent. Premièrement, sur la convergence de l’approximation entropique discrète et nous suivons ici les travaux récents de Berman et en particulier les exigences de discrétisation qui y sont imposées. Deuxièmement, nous montrons que la correction du biais induit par le transport entropique Optimal peut être atteinte en utilisant la notion récente de divergences Sinkhorn. Pour le problème de source ponctuelle, nous discutons des outils mathématiques et numériques nécessaires pour produire et analyser les résultats numériques obtenus. Nous trouvons que l’algorithme Sinkhorn peut être adapté à la résolution du problème de la source ponctuelle au réflecteur en champ lointain.Nous ne connaissons pas de formulation mathématique similaire dans le cas de la source étendue : la distribution de lumière source a support sur l’espace produit: domaine physique-directions des rayons. Nous proposons de tirer parti de la formulation variationnelle bien posée du problème de source ponctuelle pour construire une paramétrisation lisse du réflecteur et de l’application modélisant la réflexion. Sous cette paramétrisation, nous pouvons construire une fonction de coût lisse à optimiser pour trouver la meilleure solution dans cette classe de réflecteurs. Les deux étapes, la paramétrisation et la fonction de coût, sont liées à des distances de transport entropiques optimales. Nous profitons également des progrès récents des techniques d’optimisation et des implémentations efficaces de l’algorithme Sinkhorn pour réaliser une étude numérique.

Published
2021
Full Text
View/download PDF

11. Point Source Regularization of the Finite Source Reflector Problem

Author

Benamou, Jean-David, Chazareix, Guillaume, Rukhaia, Giorgi, Ijzerman, Wilbert, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Signify Research, Scientific Computing, Computational Illumination Optics, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris

Subjects
Computational Mathematics, Numerical Analysis, Optimal transportation, Physics and Astronomy (miscellaneous), Inverse reflector problem, Non-linear optimization, Applied Mathematics, Modeling and Simulation, Inverse reflector problem, 2000 MSC: 78A46, 49Q22, 65K10, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Computer Science Applications
Abstract

International audience; We address the “freeform optics” inverse problem of designing a reflector surface mapping a prescribed source distribution of light to a prescribed far field distribution, for a finite light source. When the finite source reduces to a point source, the light source distribution has support only on the optics ray directions. In this setting the inverse problem is well posed for arbitrary source and target probability distributions. It can be recast as an Optimal Transportation problem and has been studied both mathematically and nu-merically. We are not aware of any similar mathematical formulation in the finite source case: i.e. the source has an “´etendue” with support both in space and directions. We propose to leverage the well-posed variational formulation of the point source problem to build a smooth parameterization of the reflec-tor and the reflection map. Under this parameterization we can construct a smooth loss/misfit function to optimize for the best solution in this class of reflectors. Both steps, the parameterization and the loss, are related to Optimal Transportation distances. We also take advantage of recent progress in the numerical approximation and resolution of these mathematical objects to perform a numerical study.

Published
2021

12. Computation of optimal transport with finite volumes

Author

Andrea Natale, Gabriele Todeschi, Reliable numerical approximations of dissipative systems (RAPSODI ), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, GT acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 754362. AN acknowledges that this work was supported by a public grant as part of the Investissement d’avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH., ANR-11-LABX-0056,LMH,LabEx Mathématique Hadamard(2011), Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Inria Lille - Nord Europe, Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), GT acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 754362., GT acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement N° 754362. AN acknowledges that this work was supported by a public grant as part of the Investissement d'avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH., European Project: 754362,MathInParis(2017), and GT acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement N° 754362.

Subjects
Computation, Barrier method, 010103 numerical & computational mathematics, Type (model theory), 01 natural sciences, Convexity, Quadratic equation, Convergence (routing), FOS: Mathematics, Applied mathematics, Polygon mesh, Mathematics - Numerical Analysis, 0101 mathematics, [MATH]Mathematics [math], Mathematics, Numerical Analysis, Finite volume method, Finite volumes, Applied Mathematics, Dynamical optimal transport, Numerical Analysis (math.NA), 010101 applied mathematics, Computational Mathematics, Modeling and Simulation, Analysis, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], 65N08, 35A15, 65K10, 49M29, 90C51
Abstract

International audience; We construct Two-Point Flux Approximation (TPFA) finite volume schemes to solve the quadratic optimal transport problem in its dynamic form, namely the problem originally introduced by Benamou and Brenier. We show numerically that these type of discretizations are prone to form instabilities in their more natural implementation, and we propose a variation based on nested meshes in order to overcome these issues. Despite the lack of strict convexity of the problem, we also derive quantitative estimates on the convergence of the method, at least for the discrete potential and the discrete cost. Finally, we introduce a strategy based on the barrier method to solve the discrete optimization problem.

Published
2021

13. Impact of Missing Data on Mixtures and Clustering

Author

Biernacki, Christophe, Boyer, Claire, Celeux, Gilles, Josse, Julie, Laporte, Fabien, Marbac Lourdelle, Matthieu, Sportisse, Aude, Vandewalle, Vincent, MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Statistique mathématique et apprentissage (CELESTE), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria), Génétique Quantitative et Evolution - Le Moulon (Génétique Végétale) (GQE-Le Moulon), AgroParisTech-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz] (ENSAI), Modèles et algorithmes pour l’intelligence artificielle (MAASAI), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (LJAD), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Biernacki, Christophe, Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (JAD), Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
[STAT.ME] Statistics [stat]/Methodology [stat.ME], [STAT.ME]Statistics [stat]/Methodology [stat.ME], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2021

14. Nonnegative Matrix Factorization with Side Information for Time Series Recovery and Prediction

Author

Yohann De Castro, Jiali Mei, Georges Hébrail, Jean-Marc Azaïs, Yannig Goude, Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), EDF (EDF), Laboratoire de Business Intelligence Télécom-ParisTech/EDF (BILab), Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom ParisTech-Telecom Orange-EDF (EDF), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
FOS: Computer and information sciences, Computer science, Machine Learning (stat.ML), 02 engineering and technology, Statistics - Applications, 01 natural sciences, Matrix decomposition, Non-negative matrix factorization, 010104 statistics & probability, Kernel (linear algebra), Matrix (mathematics), [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Statistics - Machine Learning, 0202 electrical engineering, electronic engineering, information engineering, Applications (stat.AP), 0101 mathematics, Time series, Series (mathematics), 020206 networking & telecommunications, Computer Science Applications, Computational Theory and Mathematics, [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], Convex optimization, Identifiability, Algorithm, Information Systems
Abstract

International audience; Motivated by the reconstruction and the prediction of electricity consumption, we extend Nonnegative Matrix Factorization~(NMF) to take into account side information (column or row features). We consider general linear measurement settings, and propose a framework which models non-linear relationships between features and the response variables. We extend previous theoretical results to obtain a sufficient condition on the identifiability of the NMF in this setting. Based the classical Hierarchical Alternating Least Squares~(HALS) algorithm, we propose a new algorithm (HALSX, or Hierarchical Alternating Least Squares with eXogeneous variables) which estimates the factorization model. The algorithm is validated on both simulated and real electricity consumption datasets as well as a recommendation dataset, to show its performance in matrix recovery and prediction for new rows and columns.

Published
2019

15. Lecture notes on non-convex algorithms for low-rank matrix recovery

Author

Waldspurger, Irène, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris

Subjects
Mathematics - Statistics Theory, [MATH]Mathematics [math], Mathematics - Optimization and Control
Abstract

Low-rank matrix recovery problems are inverse problems which naturally arise in various fields like signal processing, imaging and machine learning. They are non-convex and NP-hard in full generality. It is therefore a delicate problem to design efficient recovery algorithms and to provide rigorous theoretical insights on the behavior of these algorithms. The goal of these notes is to review recent progress in this direction for the class of so-called "non-convex algorithms", with a particular focus on the proof techniques. Although they aim at presenting very recent research works, these notes have been written with the intent to be, as much as possible, accessible to non-specialists. These notes were written for an eight-hour lecture at Collège de France. The original version, in French, is available online 1 and the videos of the lecture can be found on the Collège de France website 2. The beginning takes inspiration from the review articles [Davenport and Romberg, 2016] and [Chen and Chi, 2018].

Published
2021

16. Dealing with missing data in model-based clustering through a MNAR model

Author

Biernacki, Christophe, Boyer, Claire, Celeux, Gilles, Josse, Julie, Laporte, Fabien, Lourdelle, Matthieu, Sportisse, Aude, MOdel for Data Analysis and Learning (MODAL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Statistique mathématique et apprentissage (CELESTE), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria), Génétique Quantitative et Evolution - Le Moulon (Génétique Végétale) (GQE-Le Moulon), AgroParisTech-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Ecole Nationale Supérieure des Sciences Agro-Industrielles [Univ Ngaoundéré] (ENSAI), Université de Ngaoundéré/University of Ngaoundéré [Cameroun] (UN), Modèles et algorithmes pour l’intelligence artificielle (MAASAI), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (JAD), Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (LJAD), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, and Biernacki, Christophe

Subjects
[STAT.ME] Statistics [stat]/Methodology [stat.ME], [STAT.ME]Statistics [stat]/Methodology [stat.ME], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2021

17. Optimal transportation, modelling and numerical simulation

Author

Jean-David Benamou, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
010101 applied mathematics, Numerical Analysis, Mathematical optimization, Computer simulation, Computer science, General Mathematics, Numerical analysis, 010102 general mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], 0101 mathematics, 01 natural sciences
Abstract

International audience; We present an overviewof the basic theory, modern optimal transportation extensions and recent algorithmic advances. Selected modelling and numerical applications illustrate the impact of optimal transportation in numerical analysis.

Published
2021

18. Towards Off-the-grid Algorithms for Total Variation Regularized Inverse Problems

Author

Yohann de Castro, Vincent Duval, Romain Petit, Institut Camille Jordan (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Probabilités, statistique, physique mathématique (PSPM), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This work was supported by a grant from Région Ile-De-France and by the ANR CIPRESSI project, grant ANR-19-CE48-0017-01 of the French Agence Nationale de la Recherche., Elmoataz, Abderrahim, Fadili, Jalal, Quéau, Yvain, Rabin, Julien, Simon, Loïc, ANR-19-CE48-0017,CIPRESSI,Traitement d'images continues: modèles et algorithmes(2019), Institut Camille Jordan [Villeurbanne] (ICJ), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Université de Lyon, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Réseaux dynamiques : approche structurelle et temporelle (DANTE), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, and Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Statistics and Probability, Signal Processing (eess.SP), Inverse problems, 0211 other engineering and technologies, Structure (category theory), 02 engineering and technology, Variation (game tree), 01 natural sciences, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Simple (abstract algebra), FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Off-the-grid imaging, Mathematics - Numerical Analysis, 0101 mathematics, Electrical Engineering and Systems Science - Signal Processing, Linear combination, Mathematics - Optimization and Control, Mathematics, Total variation, 021103 operations research, Off-the-grid, Applied Mathematics, 010102 general mathematics, Numerical Analysis (math.NA), Inverse problem, Condensed Matter Physics, Optimization and Control (math.OC), Modeling and Simulation, Piecewise, Geometry and Topology, Computer Vision and Pattern Recognition, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Constant (mathematics), Algorithm, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

We introduce an algorithm to solve linear inverse problems regularized with the total (gradient) variation in a gridless manner. Contrary to most existing methods, that produce an approximate solution which is piecewise constant on a fixed mesh, our approach exploits the structure of the solutions and consists in iteratively constructing a linear combination of indicator functions of simple polygons., For the short conference version see arXiv:2104.06706v2. For the long journal version see arXiv:2104.06706v5

Published
2021

19. Stability in Gagliardo-Nirenberg-Sobolev inequalities: flows, regularity and the entropy method

Author

Bonforte, Matteo, Dolbeault, Jean, Nazaret, Bruno, Simonov, Nikita, Instituto de Ciencias Matemàticas [Madrid] (ICMAT), Universidad Autónoma de Madrid (UAM)-Consejo Superior de Investigaciones Científicas [Madrid] (CSIC)-Universidad Complutense de Madrid = Complutense University of Madrid [Madrid] (UCM)-Universidad Carlos III de Madrid [Madrid] (UC3M), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), SAMM - Statistique, Analyse et Modélisation Multidisciplinaire (SAmos-Marin Mersenne) (SAMM), Université Paris 1 Panthéon-Sorbonne (UP1), Fédération Parisienne de Modélisation Mathématique (FP2M), Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Project MTM2017-85757-P (Ministry of Science and Innovation, Spain) and the Spanish Ministry of Science and Innovation, through the 'Severo Ochoa Programme for Centres of Excellence in R&D' (CEX2019-000904-S)E.U. H2020 MSCA programme, grant agreement 777822Project EFI (ANR-17-CE40-0030) of the French National Research Agency (ANR)Inria Mokaplan teamDIM Math-Innov of the Region Île-de-France, ANR-17-CE40-0030,EFI,Entropie, flots, inégalités(2017), European Project: 777822,GHAIA(2017), Universidad Autonoma de Madrid (UAM)-Consejo Superior de Investigaciones Científicas [Madrid] (CSIC)-Universidad Complutense de Madrid = Complutense University of Madrid [Madrid] (UCM)-Universidad Carlos III de Madrid [Madrid] (UC3M), Statistique, Analyse et Modélisation Multidisciplinaire (SAmos-Marin Mersenne) (SAMM), Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)

Subjects
intermediate asymptotics, Mathematics::Analysis of PDEs, fast diffusion equation, rates of convergence, stability, Harnack Principle, 26D10, 46E35, 35K55, 49J40, 35B40, 49K20, 49K30, 35J20, Mathematics - Analysis of PDEs, Hardy-Poincaré inequalities, spectral gap, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], self-similar Barenblatt solutions, asymptotic behavior, 2020 Mathematics Subject Classification.26D10, 46E35, 35K55, 49J40, 35B40, 49K20, 49K30, 35J20, Gagliardo-Nirenberg inequality, Analysis of PDEs (math.AP), entropy methods
Abstract

The purpose of this work is to establish a quantitative and constructive stability result for a class of subcritical Gagliardo-Nirenberg-Sobolev inequalities which interpolates between the logarithmic Sobolev inequality and the standard Sobolev inequality (in dimension larger than three), or Onofri's inequality in dimension two. We develop a new strategy, in which the flow of the fast diffusion equation is used as a tool: a stability result in the inequality is equivalent to an improved rate of convergence to equilibrium for the flow. The regularity properties of the parabolic flow allow us to connect an improved entropy - entropy production inequality during an initial time layer to spectral properties of a suitable linearized problem which is relevant for the asymptotic time layer. Altogether, the stability in the inequalities is measured by a deficit which controls in strong norms (a Fisher information which can be interpreted as a generalized Heisenberg uncertainty principle) the distance to the manifold of optimal functions. The method is constructive and, for the first time, quantitative estimates of the stability constant are obtained, including in the critical case of Sobolev's inequality. To build the estimates, we establish a quantitative global Harnack principle and perform a detailed analysis of large time asymptotics by entropy methods., Comment: This manuscript merges 2007.03674: Stability in Gagliardo-Nirenberg inequalities and 2007.03419: Stability in Gagliardo-Nirenberg inequalities. Supplementary material with several additions including: Chapter 1 (variational methods) and Chapter 6 (Sobolev's inequality)

Published
2021

20. On the linear convergence of the multi-marginal Sinkhorn algorithm

Author

Carlier, Guillaume, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
Linear convergence, Sinkhorn algorithm, MS Classification: 45G15, 49M05, Block coordinate descent, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Multi-marginal entropic optimal transport
Abstract

International audience; The aim of this short note is to give an elementary proof of linear convergence of the Sinkhorn algorithm for the entropic regularization of multi-marginal optimal transport. The proof simply relies on: i) the fact that Sinkhorn iterates are bounded, ii) strong convexity of the exponential on bounded intervals and iii) the convergence analysis of the coordinate descent (Gauss-Seidel) method of Beck and Tetruashvili [1].

Published
2021

21. 'FISTA' in Banach spaces with adaptive discretisations

Author

Antonin Chambolle, Robert Tovey, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), R.T. acknowledges funding from EPSRC grant EP/L016516/1 for the Cambridge Centre for Analysis,and the ANR CIPRESSI project grant ANR-19-CE48-0017-01 of the French Agence Nationale de laRecherch, ANR-19-CE48-0017,CIPRESSI,Traitement d'images continues: modèles et algorithmes(2019), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, R.T. acknowledges funding from EPSRC grant EP/L016516/1 for the Cambridge Centre for Analysis,and the ANR CIPRESSI project grant ANR-19-CE48-0017-01 of the French Agence Nationale de la Recherche., Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)

Subjects
Multiscale, Computational Mathematics, Control and Optimization, Optimization and Control (math.OC), Applied Mathematics, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Multigrid, Lasso, Mathematics - Optimization and Control, Sparsity, Convex optimization
Abstract

FISTA is a popular convex optimisation algorithm which is known to converge at an optimal rate whenever a minimiser is contained in a suitable Hilbert space. We propose a modified algorithm where each iteration is performed in a subset which is allowed to change at every iteration. Sufficient conditions are provided for guaranteed convergence, although at a reduced rate depending on the conditioning of the specific problem. These conditions have a natural interpretation when a minimiser exists in an underlying Banach space. Typical examples are L1-penalised reconstructions where we provide detailed theoretical and numerical analysis., Accepted version

Published
2021

22. Entropic-Wasserstein barycenters: PDE characterization, regularity and CLT

Author

Katharina Eichinger, Guillaume Carlier, Alexey Kroshnin, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), GC is grateful to the Agence Nationale de la Recherche for its support through the projects MAGA (ANR-16-CE40-0014) and MFG( ANR-16-CE40-0015-01). KE acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 754362.The work of Alexey Kroshnin is supported by Russian Science Foundationgrant No. 18-71-10108, PSL Université Paris Dauphine, Université Claude Bernard - Lyon 1 Institut Camille Jordan - CNRS UMR 5208, Inria Paris, ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016), ANR-16-CE40-0015,MFG,Jeux Champs Moyen(2016), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut Camille Jordan (ICJ), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Pure mathematics, Central limit theorem, Mathematics::General Topology, Statistics::Other Statistics, Characterization (mathematics), Entropic-Wasserstein barycenters, 01 natural sciences, Monge-Ampère equations and systems, Mathematics - Analysis of PDEs, FOS: Mathematics, Mathematics::Metric Geometry, 49Q25, 35J96, 60B12, 0101 mathematics, Mathematics, MS Classification: 49Q25, 35J96, 60B12, Applied Mathematics, 010102 general mathematics, Mathematical analysis, Probability (math.PR), 010101 applied mathematics, Computational Mathematics, Astrophysics::Earth and Planetary Astrophysics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Analysis, Mathematics - Probability, Analysis of PDEs (math.AP)
Abstract

In this paper, we investigate properties of entropy-penalized Wasserstein barycenters introduced by Bigot, Cazelles and Papadakis (2019) as a regularization of Wasserstein barycenters first presented by Agueh and Carlier (2011). After characterizing these barycenters in terms of a system of Monge-Amp\`ere equations, we prove some global moment and Sobolev bounds as well as higher regularity properties. We finally establish a central limit theorem for entropic-Wasserstein barycenters.

Published
2021

23. A mean field game model for the evolution of cities

Author

Guillaume Carlier, Jean-Michel Lasry, César Barilla, Columbia University [New York], CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL), G.C. is grateful to the Agence Nationale de la Recherche for its support through the projects MAGA (ANR-16-CE40-0014) and MFG (ANR-16-CE40-0015-01)., ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016), ANR-16-CE40-0015,MFG,Jeux Champs Moyen(2016), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Statistics and Probability, Iterative Proportional Fitting procedure (IPFP), Mean field game, 01 natural sciences, Competition (economics), symbols.namesake, Quadratic equation, Optimal transport, Applied mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], 0101 mathematics, Mean field games, Mathematics, Labour market equilibrium, MS Classification: 49L05, 65K10, 91A14, Convex duality, Economies of agglomeration, Applied Mathematics, Equilibrium conditions, 010102 general mathematics, Regular polygon, Coupling (probability), 010101 applied mathematics, Modeling and Simulation, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Lagrangian
Abstract

International audience; We propose a (toy) MFG model for the evolution of residents and firms densities, coupled both by labour market equilibrium conditions and competition for land use (congestion). This results in a system of two Hamilton-Jacobi-Bellman and two Fokker-Planck equations with a new form of coupling related to optimal transport. This MFG has a convex potential which enables us to find weak solutions by a variational approach. In the case of quadratic Hamiltonians, the problem can be reformulated in Lagrangian terms and solved numerically by an IPFP/Sinkhorn-like scheme as in [4]. We present numerical results based on this approach, these simulations exhibit different behaviours with either agglomeration or segregation dominating depending on the initial conditions and parameters.

Published
2021

24. Relaxations Semi-définies Positives pour l'Imagerie

Author

Catala, Paul, Département de Mathématiques et Applications - ENS Paris (DMA), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Ecole Normale Supérieure, Gabriel PEYRE, Vincent DUVAL, École normale supérieure - Paris (ENS Paris), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
BLASSO, Parcimonie, Prony’s method, Moment matrices, Méthode de Prony, Distances de Wasserstein, Trigonometric moments, Lasserre’s hierarchy, Frank-Wolfe, Wasserstein distances, Programmation SDP, Matrices de moments, Transport optimal, Moments trigonométriques, Super-resolution, Hiérarchies de Lasserre, Optimal transport, Super-résolution, Semidefinite programming, Burer-Monteiro, [MATH]Mathematics [math], Sparsity
Abstract

This thesis proposes theoretical and algorithmic advances for positive semi-definite relaxations and their applications in data science. These so-called Lasserre’s hierarchies allow one to solve super-resolution problems without resorting to spatial discretization, by replacing measures with their trigonometric moments. However, they require the resolution of large convex optimization problems. The contributions of this thesis show how to scale these methods by exploiting certain properties and invariances of imaging problems. We first propose a new approach for the recovery of continuous measures from a finite number of moments, based on the approximate joint-diagonalization of a few non-Hermitian matrices. Then, we study the super-resolution problem, and its approximation by Lasserre’s hierarchy. A preliminary step consisting in the spectral projection of the forward operator makes this approximation possible, and further allows a fast implementation, the Fourier-based Frank Wolfe (FFW), taking advantage of the convolutional and low-rank structure of the involved matrices. We apply our method on fluorescence microscopy data. Finally, combining the recovery of continuous measures with the fast implementation of FFW, we employ Lasserre’s hierarchies to approximate the optimal transport between measures, which can also be coupled with the Blasso.; Cette thèse propose des avancées théoriques et algorithmiques pour les relaxations semi-définies positives et leurs applications en science des données. Ces relaxations, dites de Lasserre, fondées sur la substitution aux mesures boréliennes de leurs moments trigonométriques, permettent de résoudre des problèmes de super-résolution sans discrétisation spatiale, mais nécessitent en contrepartie la résolution de problèmes d’optimisation convexe de grande taille. Les contributions de cette thèse montrent comment faire passer ces méthodes à l’échelle en exploitant certaines propriétés et invariances des problèmes d’imagerie. Nous proposons dans un premier temps une nouvelle méthode pour la reconstruction de mesures continues à partir d’un nombre fini de leurs moments, reposant sur un algorithme de co-diagonalisation approchée. Nous étudions ensuite le problème de super-résolution, sous sa forme variationnelle appelée BLASSO, et son approximation par la hiérarchie de Lasserre. Une étape préalable de projection spectrale de l’opérateur d’acquisition rend possible cette approximation et permet également son implémentation efficace via un nouvel algorithme, le Fourier-based Frank-Wolfe (FFW), tirant profit de la structure convolutive et de faible rang des matrices impliquées. Nous appliquons notre méthode sur des données de microscopie par fluorescence. Enfin, combinant la reconstruction de mesures continues avec l’implémentation rapide de FFW, nous employons les hiérarchies de Lasserre afin d’approcher le transport optimal entre deux mesures, qui peut également être couplé avec le Blasso.

Published
2020

25. Rank Optimality for the Burer-Monteiro Factorization

Author

Alden Waters, Irène Waldspurger, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS), Bernoulli Institute for Mathematics and Computer Science and Artificial Intelligence, University of Groningen [Groningen], A.W. acknowledges support by EPSRC grant EP/L01937X/1, Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, and Systems, Control and Applied Analysis

Subjects
Semidefinite programming, 021103 operations research, Rank (linear algebra), Heuristic, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Combinatorics, Factorization, Full matrix, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, Mathematics - Optimization and Control, Software, Mathematics
Abstract

When solving large scale semidefinite programs that admit a low-rank solution, an efficient heuristic is the Burer-Monteiro factorization: instead of optimizing over the full matrix, one optimizes over its low-rank factors. This reduces the number of variables to optimize, but destroys the convexity of the problem, thus possibly introducing spurious second-order critical points. The article [Boumal, Voroninski, and Bandeira, 2018] shows that when the size of the factors is of the order of the square root of the number of linear constraints, this does not happen: for almost any cost matrix, second-order critical points are global solutions. In this article, we show that this result is essentially tight: for smaller values of the size, second-order critical points are not generically optimal, even when the global solution is rank 1., Comment: Simplified results and proofs

Published
2020

26. Explicit constants in Harnack inequalities and regularity estimates, with an application to the fast diffusion equation

Author

Bonforte, Matteo, Dolbeault, Jean, Nazaret, Bruno, Simonov, Nikita, Universidad Autonoma de Madrid (UAM), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL), Statistique, Analyse et Modélisation Multidisciplinaire (SAmos-Marin Mersenne) (SAMM), Université Paris 1 Panthéon-Sorbonne (UP1), Fédération Parisienne de Modélisation Mathématique (FP2M), Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, ANR-17-CE40-0030,EFI,Entropie, flots, inégalités(2017), Universidad Autónoma de Madrid (UAM), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
Entropy methods, Rates of convergence, Self-similar Barenblatt solutions, Moser's Harnack inequality, MathematicsofComputing_NUMERICALANALYSIS, Harnack Principle, Asymptotic behavior, Fast diffusion equation, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], 26D10, 46E35, 35K55, 49J40, 35B40, 49K20, 49K30, 35J20, Intermediate asymptotics, Stability, Gagliardo-Nirenberg inequality
Abstract

This paper is devoted to the computation of various explicit constants in functional inequalities and regularity estimates for solutions of parabolic equations, which are not available from the literature. We provide new expressions and simplified proofs of the Harnack inequality and the corresponding Hölder continuity of the solution of a linear parabolic equation. We apply these results to the computation of a constructive estimate of a threshold time for the uniform convergence in relative error of the solution of the fast diffusion equation.

Published
2020

27. TPFA Finite Volume Approximation of Wasserstein Gradient Flows

Author

Andrea Natale, Gabriele Todeschi, Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), The work of A. Natale was supported by the European Research Council (ERC project NORIA). Gabriele Todeschi acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 754362., CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Finite volume method, Discretization, Dynamical systems theory, Numerical Analysis (math.NA), 010103 numerical & computational mathematics, Space (mathematics), 01 natural sciences, 010101 applied mathematics, Wasserstein gradient flows, Energy diminishing scheme, Rate of convergence, FOS: Mathematics, Applied mathematics, Point (geometry), Mathematics - Numerical Analysis, 0101 mathematics, Balanced flow, Interior point method, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Mathematics
Abstract

International audience; Numerous infinite dimensional dynamical systems arising in different fields have been shown to exhibit a gradient flow structure in the Wasserstein space. We construct Two Point Flux Approximation Finite Volume schemes discretizing such problems which preserve the variational structure and have second order accuracy in space. We propose an interior point method to solve the discrete variational problem, providing an efficient and robust algorithm. We present two applications to test the scheme and show its order of convergence.

Published
2020

28. Existence of solutions to principal–agent problems with adverse selection under minimal assumptions

Author

Guillaume Carlier, Kelvin Shuangjian Zhang, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Département de Mathématiques et Applications - ENS Paris (DMA), École normale supérieure - Paris (ENS-PSL), Guillaume Carlier is grateful to the Agence Na-tionale de la Recherche for its support through the projects MAGA (ANR-16-CE40-0014) and MFG (ANR-16-CE40-0015-01). Kelvin Shuangjian Zhang is thankful for the support of Mitacs Globalink Research, ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016), ANR-16-CE40-0015,MFG,Jeux Champs Moyen(2016), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, and Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
Economics and Econometrics, Mathematical optimization, Partial participation, Computer science, Applied Mathematics, 05 social sciences, Principal (computer security), Principal–agent problem, Adverse selection, Space (mathematics), Coercivity, [SHS]Humanities and Social Sciences, Principal-agent problems with adverse selection, Simple (abstract algebra), Budget constraint, 0502 economics and business, 050206 economic theory, 050205 econometrics
Abstract

International audience; We prove an existence result for the principal-agent problem with adverse selection under general assumptions on preferences and allo-cation spaces. Instead of assuming that the allocation space is finite-dimensional or compact, we consider a more general coercivity condi-tion which takes into account the principal’s cost and the agents’ pref-erences. Our existence proof is simple and flexible enough to adapt to partial participation models as well as to the case of type-dependent budget constraints.

Published
2020

29. Capacity Constrained Entropic Optimal Transport, Sinkhorn Saturated Domain Out-Summation and Vanishing Temperature

Author

Benamou, Jean-David, Martinet, Mélanie, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Entropic regularization, AMS Subject Headings : 49N99, 49J20, 65D99, 90C0, Optimal transport, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Sinkhorn Algorithm, Convex optimization
Abstract

We propose a new method to reduce the computational cost of the Entropic Optimal Transport in the vanishing temperature (ε) limit. As in [Schmitzer, 2016], the method relies on a Sinkhorn continuation "ε-scaling" approach; but instead of truncating out the small values of the Kernel, we rely on the exact "out-summation" of saturated domains for a modified constrained Entropic Optimal problem. The constraint depends on an additional parameter λ. In pratice λ = ε also vanishes and the constraint disappear. Using [Berman, 2017], the convergence of the (ε, λ) continuation method based on this modified problem is established. We then show that the saturated domain can be over estimated from the previous larger (ε, λ). On the saturated zone the solution is constant and known and the domain can be "out-summed" (removed) from Sinkhorn algorithm. The computational and cost and memory foot print is shown to be almost linear thanks again to an estimate given by [Berman, 2017]. This is confirmed on 1-D numerical experiments.

Published
2020

30. A characterization of the Non-Degenerate Source Condition in Super-Resolution

Author

Vincent Duval, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Statistics and Probability, T-Systems, Basis pursuit, 02 engineering and technology, 01 natural sciences, Stability (probability), Convolution, 010104 statistics & probability, symbols.namesake, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Numerical Analysis, 0101 mathematics, Mathematics, Numerical Analysis, Total Variation minimization, Lebesgue measure, Laplace transform, Applied Mathematics, Mathematical analysis, Degenerate energy levels, 020206 networking & telecommunications, Numerical Analysis (math.NA), 16. Peace & justice, Gaussian filter, Computational Theory and Mathematics, Kernel (image processing), $\ell^1$ norm, Super-resolution, symbols, AMS subject classifications: 90C25, 68U10, LASSO for measures, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Analysis, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience; In a recent article, Schiebinger et al. provided sufficient conditions for the noiseless recovery of a signal made of M Dirac masses given 2M + 1 observations of, e.g. , its convolution with a Gaussian filter, using the Basis Pursuit for measures. In the present work, we show that a variant of their criterion provides a necessary and sufficient condition for the Non-Degenerate Source Condition (NDSC) which was introduced by Duval and Peyré to ensure support stability in super-resolution. We provide sufficient conditions which, for instance, hold unconditionally for the Laplace kernel provided one has at least 2M measurements. For the Gaussian filter, we show that those conditions are fulfilled in two very different configurations: samples which approximate the uniform Lebesgue measure or, more surprisingly, samples which are all confined in a sufficiently small interval.

Published
2020

31. Generalized compressible flows and solutions of the H(div) geodesic problem

Author

Thomas Gallouët, Andrea Natale, François-Xavier Vialard, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016), European Project: 609102,EC:FP7:PEOPLE,FP7-PEOPLE-2013-COFUND,PRESTIGE(2014), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Pure mathematics, Geodesic, Space (mathematics), 01 natural sciences, symbols.namesake, Mathematics - Analysis of PDEs, Mathematics (miscellaneous), FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Mathematics - Numerical Analysis, 0101 mathematics, Mathematics, Probability measure, Mechanical Engineering, 010102 general mathematics, Numerical Analysis (math.NA), 010101 applied mathematics, Cone (topology), Euler's formula, symbols, Diffeomorphism, Relaxation (approximation), Solving the geodesic equations, Analysis, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Analysis of PDEs (math.AP)
Abstract

We study the geodesic problem on the group of diffeomorphism of a domain $$M\subset {\mathbb {R}}^d$$, equipped with the $$H(\mathrm {div})$$ metric. The geodesic equations coincide with the Camassa–Holm equation when $$d=1$$, and represent one of its possible multi-dimensional generalizations when $$d>1$$. We propose a relaxation a la Brenier of this problem, in which solutions are represented as probability measures on the space of continuous paths on the cone over M. We use this relaxation to prove that smooth $$H(\mathrm {div})$$ geodesics are globally length minimizing for short times. We also prove that there exists a unique pressure field associated to solutions of our relaxation. Finally, we propose a numerical scheme to construct generalized solutions on the cone and present some numerical results illustrating the relation between the generalized Camassa–Holm and incompressible Euler solutions.

Published
2020

32. High frequency limit for a chain of harmonic oscillators with a point Langevin thermostat

Author

Herbert Spohn, Tomasz Komorowski, Lenya Ryzhik, Stefano Olla, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Department of Mathematics [Stanford], Stanford University, Centre fo Mathematical Sciences (D-MUTU-ZM), Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), This work was partially supported by the grant 346300 for IMPAN from the Simons Foundation and the matching 2015-2019 Polish MNiSW fund., ANR-15-CE40-0020,LSD,Modèles stochastiques en grande dimension pour la physique statistique hors équilibre(2015), Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics, Stanford University [Stanford], Technische Universität München [München] (TUM), ANR-15-CE40-0020,LSD,Large Stochastic Dynamical Models in Non-Equilibrium Statistical Physics(2015), CEntre de REcherches en MAthématiques de la DEcision ( CEREMADE ), Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ), Centre fo Mathematical Sciences ( D-MUTU-ZM ), Technische Universität München [München] ( TUM ), and ANR-15-CE40-0020,LSD,Large Stochastic Dynamical Models in Non-Equilibrium Statistical Physics ( 2015 )

Subjects
82C21, Complex system, FOS: Physical sciences, 01 natural sciences, law.invention, Mathematics (miscellaneous), Chain (algebraic topology), law, Computer Science::Systems and Control, [MATH.MATH-MP]Mathematics [math]/Mathematical Physics [math-ph], Wigner distribution, Limit (music), Langevin thermostats, FOS: Mathematics, Wigner distribution function, 0101 mathematics, [PHYS.COND.CM-SM]Physics [physics]/Condensed Matter [cond-mat]/Statistical Mechanics [cond-mat.stat-mech], energy transport, Harmonic oscillator, Mathematical Physics, Condensed Matter - Statistical Mechanics, Physics, Statistical Mechanics (cond-mat.stat-mech), Scattering, Mechanical Engineering, 010102 general mathematics, Probability (math.PR), [ MATH.MATH-MP ] Mathematics [math]/Mathematical Physics [math-ph], Mathematical Physics (math-ph), High frequency limit, Thermostat, 010101 applied mathematics, Nonlinear Sciences::Chaotic Dynamics, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], [ PHYS.COND.CM-SM ] Physics [physics]/Condensed Matter [cond-mat]/Statistical Mechanics [cond-mat.stat-mech], Quantum electrodynamics, Condensed Matter::Statistical Mechanics, [ MATH.MATH-PR ] Mathematics [math]/Probability [math.PR], Analysis, Energy (signal processing), Mathematics - Probability
Abstract

International audience; We consider an infinite chain of coupled harmonic oscillators with a Langevin thermostat at the origin. In the high frequency limit, we establish the reflection-transmission coefficients for the wave energy for the scattering of the thermostat. To our surprise, even though the thermostat fluctuations are time-dependent, the scattering does not couple wave energy at various frequencies.

Published
2020

33. A differential approach to the multi-marginal Schrödinger system

Author

Guillaume Carlier, Maxime Laborde, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Mathematics and Statistics [Montréal], McGill University = Université McGill [Montréal, Canada], ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
Applied Mathematics, Mathematical analysis, Mathematics::Analysis of PDEs, [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], 01 natural sciences, 010101 applied mathematics, Mathematics - Functional Analysis, Computational Mathematics, symbols.namesake, 45G15, 49K40, Mathematics - Analysis of PDEs, Multi-marginal Schrödinger system, Local and global inverse function theorems, symbols, Entropy minimization, Uniqueness, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, Analysis, Schrödinger's cat, Mathematics
Abstract

International audience; We develop an elementary and self-contained differential approach, in an L ∞ setting, for well-posedness (existence, uniqueness and smooth dependence with respect to the data) for the multi-marginal Schrödinger system which arises in the entropic regularization of optimal transport problems.

Published
2020

34. Some new Stein operators for product distributions

Author

Yvik Swan, Guillaume Mijoule, Robert E. Gaunt, University of Manchester [Manchester], Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Liège, Robert E. Gaunt acknowledges support from EPSRC grant EP/K032402/1 and is currently supported by a Dame Kathleen Ollerenshaw Research Fellowship. Robert E. Gaunt is grateful to Université de Liège, FNRS and EPSRC for funding a visit to University de Liège, where some of thedetails of this project were worked out. Yvik Swan gratefully acknowledges support by the Fonds de la Recherch e Scientifique - FNRS under Grant MIS F.4539.16. Part of GM’s research was supported by a WG (Welcome Grant) from Université de Liège, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
Statistics and Probability, Stein operators, Pure mathematics, Characteristic function (probability theory), Product of independent normal random variables, Probability density function, Stein’s method, 01 natural sciences, AMS 2010 Subject Classification: Primary 60F05, Secondary 62E15, 010104 statistics & probability, Simple (abstract algebra), FOS: Mathematics, Statistique mathématique, 0101 mathematics, Mathematics, Probability (math.PR), 010102 general mathematics, Product distributions, Primary 60F05, Secondary 62E15, Stein's method, Probabilités, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Distribution (mathematics), Product (mathematics), Random variable, Mathematics - Probability
Abstract

We provide a general result for finding Stein operators for the product of two independent random variables whose Stein operators satisfy a certain assumption, extending a recent result of Gaunt, Mijoule and Swan \cite{gms18}. This framework applies to non-centered normal and non-centered gamma random variables, as well as a general sub-family of the variance-gamma distributions. Curiously, there is an increase in complexity in the Stein operators for products of independent normals as one moves, for example, from centered to non-centered normals. As applications, we give a simple derivation of the characteristic function of the product of independent normals, and provide insight into why the probability density function of this distribution is much more complicated in the non-centered case than the centered case., Comment: 18 pages. To appear in Brazilian Journal of Probability and Statistics, 2019+

Published
2020

35. An Entropic Optimal Transport Numerical Approach to the Reflector Problem

Author

Jean-David Benamou, Giorgi Rukhaia, Wilbert Ijzerman, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Eindhoven University of Technology [Eindhoven] (TU/e), This work was supported by ROMSOC EID H2020 network under the Marie Curie Grant Agreement No. 765374, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Work (thermodynamics), Optimal transportation, Discretization, Reflector (antenna), Extension (predicate logic), Resolution (logic), Displacement (vector), Non-linear optimization, Simple (abstract algebra), Inverse reflector problem, Convergence (routing), Applied mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 2010 Mathematics Subject Classification49Qxx, 65K10, 78A46, Mathematics
Abstract

The point source far field reflector design problem is one of the main classic optimal transport problems with a non-euclidean displacement cost [Wang, 2004] [Glimm and Oliker, 2003].This work describes the use of Entropic Optimal Transport and the associated Sinkhorn algorithm [Cuturi, 2013] to solve it numerically. As the reflector modelling is based on the Kantorovich potentials, several questions arise. First, on the convergence of the discrete entropic approximation and here we follow the recent work of [Berman, 2017] and in particular the imposed discretization requirements therein. Secondly, the correction of the Entropic bias induced by the Entropic OT, as discussed inparticular in [Ramdas et al., 2017] [Genevay et al., 2018] [Feydy et al., 2018], is another important tool to achieve reasonable results. The paper reviews the necessary mathematical and numerical tools needed to produce and discuss the obtained numerical results. We find that Sinkhorn algorithm may be adapted, at least in simple academic cases, to the resolution of the far field reflector problem. Sinkhorn canonical extension to continuous potentials is needed to generate continuous reflector approximations.The use of Sinkhorn divergences [Feydy et al., 2018] is useful to mitigate the entropic bias., working paper or preprint

Published
2020
Full Text
View/download PDF

36. An Epigraphical Approach to the Representer Theorem

Author

Duval, Vincent, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), ANR-19-CE48-0017,CIPRESSI,Traitement d'images continues: modèles et algorithmes(2019), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Signal Processing (eess.SP), Optimization and Control (math.OC), FOS: Mathematics, FOS: Electrical engineering, electronic engineering, information engineering, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Electrical Engineering and Systems Science - Signal Processing, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Mathematics - Optimization and Control
Abstract

International audience; Describing the solutions of inverse problems arising in signal or image processing is an important issue both for theoretical and numerical purposes. We propose a principle which describes the solutions to convex variational problems involving a finite number of measurements. We discuss its optimality on various problems concerning the recovery of Radon measures.

Published
2019

37. Stein operators, kernels and discrepancies for multivariate continuous distributions

Author

Mijoule, Guillaume, Reinert, Gesine, Swan, Yvik, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), University of Oxford [Oxford], Université libre de Bruxelles (ULB), G Michoule and Y Swan gratefully acknowledges support by the Fonds de la Recherche Scientifique - FNRS under Grant MIS F.4539.16. G Reinert acknowledges partial support from EPSRC grant EP/K032402/1 and the Alan Turing Institute, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and University of Oxford

Subjects
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Mathematics::Complex Variables, Probability (math.PR), FOS: Mathematics, 60B10, 60B12, Mathematics::Symplectic Geometry, Mathematics - Probability, MSC 2010 classification: 60B10, 60B12
Abstract

We present a general framework for setting up Stein's method for multivariate continuous distributions. The approach gives a collection of Stein characterizations, among which we highlight score-Stein operators and kernel-Stein operators. Applications include copu-las and distance between posterior distributions. We give a general explicit construction for Stein kernels for elliptical distributions and discuss Stein kernels in generality, highlighting connections with Fisher information and mass transport. Finally, a goodness-of-fit test based on Stein discrepancies is given.

Published
2019

38. On correctors for linear elliptic homogenization in the presence of local defects

Author

C. Le Bris, Xavier Blanc, Pierre-Louis Lions, Sorbonne Université (SU), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Université Paris Diderot - Paris 7 (UPD7)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), MATHematics for MatERIALS (MATHERIALS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Collège de France - Chaire Équations aux dérivées partielles et applications, Collège de France (CdF (institution)), Laboratoire Jacques-Louis Lions ( LJLL ), Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ), Sorbonne Universités, Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique ( CERMICS ), École des Ponts ParisTech ( ENPC ), MATHematics for MatERIALS ( MATHERIALS ), École des Ponts ParisTech ( ENPC ) -École des Ponts ParisTech ( ENPC ) -Inria de Paris, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Collège de France ( CdF ), CEntre de REcherches en MAthématiques de la DEcision ( CEREMADE ), Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Chaire Équations aux dérivées partielles et applications, Collège de France (CDF), Collège de France (CdF), and Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)

Subjects
Homogenization, Applied Mathematics, 010102 general mathematics, Mathematical analysis, Computer Science::Computational Complexity, 01 natural sciences, Homogenization (chemistry), 010101 applied mathematics, Elliptic curve, Mathematics - Analysis of PDEs, [ MATH.MATH-AP ] Mathematics [math]/Analysis of PDEs [math.AP], AMS subject classification: 35J15, 35J70, 35B27, 74Q15, 76M50, FOS: Mathematics, Lp estimates, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Defects, 0101 mathematics, Elliptic PDE, Analysis, Analysis of PDEs (math.AP), Mathematics
Abstract

We consider the corrector equation associated, in homogenization theory , to a linear second-order elliptic equation in divergence form --$\partial$i(aij$\partial$ju) = f , when the diffusion coefficient is a locally perturbed periodic coefficient. The question under study is the existence (and uniqueness) of the corrector, strictly sublinear at infinity, with gradient in L r if the local perturbation is itself L r , r < +$\infty$. The present work follows up on our works [7, 8, 9], providing an alternative, more general and versatile approach , based on an a priori estimate, for this well-posedness result. Equations in non-divergence form such as --aij$\partial$iju = f are also considered, along with various extensions. The case of general advection-diffusion equations --aij$\partial$iju + bj$\partial$ju = f is postponed until our future work [10]. An appendix contains a corrigendum to our earlier publication [9]., Communications in Partial Differential Equations, Taylor \& Francis, A Para{\^i}tre

Published
2018

39. Unbounded rough drivers

Author

Massimiliano Gubinelli, Ismael Bailleul, Institut de Recherche Mathématique de Rennes (IRMAR), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), CEntre de REcherches en MAthématiques de la DEcision ( CEREMADE ), Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Probability (math.PR), 010102 general mathematics, Mathematical analysis, MathematicsofComputing_NUMERICALANALYSIS, General Medicine, 01 natural sciences, 010104 statistics & probability, Mathematics - Analysis of PDEs, [ MATH.MATH-AP ] Mathematics [math]/Analysis of PDEs [math.AP], Linear differential equation, Symmetric systems, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, 35R60, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Vector field, 0101 mathematics, Mathematics - Probability, Analysis of PDEs (math.AP), Mathematics
Abstract

We propose a theory of linear differential equations driven by unbounded operator-valued rough signals. As an application we consider rough linear transport equations and more general linear hyperbolic symmetric systems of equations driven by time-dependent vector fields which are only distributions in the time direction., Comment: 38 pages. some improvements and precisions

Published
2017

40. Sampling the Fourier Transform Along Radial Lines

Author

Charles Dossal, Vincent Duval, Clarice Poon, Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Department of Applied Mathematics and Theoretical Physics (DAMTP), University of Cambridge [UK] (CAM), CNRS Défi Imag'In, CAVALIERI, Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete-time Fourier transform, Non-uniform discrete Fourier transform, Geometry, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Discrete Fourier transform, symbols.namesake, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Numerical Analysis, 0101 mathematics, Radon transform, Mathematics, Total variation, Numerical Analysis, Applied Mathematics, Mathematical analysis, Short-time Fourier transform, 020206 networking & telecommunications, Numerical Analysis (math.NA), Fractional Fourier transform, Computational Mathematics, Fourier transform, symbols, Compressed sensing, Harmonic wavelet transform, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Abstract

International audience; This article considers the use of total variation minimization for the recovery of a superposition of point sources from samples of its Fourier transform along radial lines. We present a numerical algorithm for the computation of solutions to this infinite dimensional problem. The theoretical results of this paper make precise the link between the sampling operator and the recoverability of the point sources.

Published
2017

41. The Sliding Frank-Wolfe Algorithm for the BLASSO

Author

Denoyelle, Quentin, Duval, Vincent, Peyré, Gabriel, Soubies, Emmanuel, Biomedical Imaging Group [Lausanne], Ecole Polytechnique Fédérale de Lausanne (EPFL), Laboratoire Traitement et Communication de l'Information (LTCI), Télécom ParisTech-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Département de Mathématiques et Applications - ENS Paris (DMA), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Signal et Communications (IRIT-SC), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Centre National de la Recherche Scientifique (CNRS), CNRS, Grélaud, Françoise, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École normale supérieure - Paris (ENS-PSL), Université Toulouse Capitole (UT Capitole), Université Fédérale Toulouse Midi-Pyrénées-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, and Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
[INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, [INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing, Traitement du signal et de l'image, [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG]
Abstract

International audience; This paper showcases the theoretical and numerical performance of the Sliding Frank-Wolfe, which is a novel optimization algorithm to solve the BLASSO sparse spikes super-resolution problem. The BLASSO is a continuous (i.e. off-the-grid or grid-less) counterpart to the well-known 1 sparse regularisation method (also known as LASSO or Basis Pursuit). Our algorithm is a variation on the classical Frank-Wolfe (also known as conditional gradient) which follows a recent trend of interleaving convex optimization updates (corresponding to adding new spikes) with non-convex optimization steps (corresponding to moving the spikes). Our main theoretical result is that this algorithm terminates in a finite number of steps under a mild non-degeneracy hypothesis. We then target applications of this method to several instances of single molecule fluorescence imaging modalities, among which certain approaches rely heavily on the inversion of a Laplace transform. Our second theoretical contribution is the proof of the exact support recovery property of the BLASSO to invert the 1-D Laplace transform in the case of positive spikes. On the numerical side, we conclude this paper with an extensive study of the practical performance of the Sliding Frank-Wolfe on different instantiations of single molecule fluorescence imaging, including convolutive and non-convolutive (Laplace-like) operators. This shows the versatility and superiority of this method with respect to alternative sparse recovery technics.

Published
2019

42. An augmented Lagrangian approach to Wasserstein gradient flows and applications

Author

Jean-David Benamou, Guillaume Carlier, Maxime Laborde, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), ANR-12-MONU-0013,ISOTACE,Systemes d'Interactions, Transport Optimal, Applications a la simulation en Economie.(2012), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Scheme (programming language), Mathematical optimization, MS Classification 2010: 49M29, 65M60, Motion (geometry), Granular media, Non-linear diffusion, 010103 numerical & computational mathematics, 01 natural sciences, Wasserstein gradient flows, QA1-939, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Non linear diffusion, Crowd motions, 0101 mathematics, Mathematics, computer.programming_language, T57-57.97, Applied mathematics. Quantitative methods, Augmented Lagrangian, Augmented Lagrangian method, Regular polygon, Systems, Benamou-Brenier formulation, Semi-implicit JKO scheme, 010101 applied mathematics, Porous medium, computer
Abstract

International audience; Taking advantage of the Benamou-Brenier dynamic formulation of optimal transport, we propose a convex formulation for each step of the JKO scheme for Wasserstein gradient flows which can be attacked by an augmented Lagrangian method which we call the ALG2-JKO scheme. We test the algorithm in particular on the porous medium equation. We also consider a semi implicit variant which enables us to treat nonlocal interactions as well as systems of interacting species. Regarding systems, we can also use the ALG2-JKO scheme for the simulation of crowd motion models with several species.

Published
2019

43. Multiple Testing and Variable Selection along Least Angle Regression's path

Author

Azaïs, Jean-Marc, De Castro, Yohann, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Probabilités, statistique, physique mathématique (PSPM), Institut Camille Jordan (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Multiple Testing, [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Post-Selection Inference, MSC 2010 subject classifications: Primary 62E15, 62F03, 60G15, 62H10, 62H15, secondary 60E05, 60G10, 62J05, 94A08, High-Dimensional Statistics, False Discovery Rate
Abstract

39 pages, 7 figures; International audience; In this article we investigate the outcomes of the standard Least Angle Regression (LAR) algorithm in high dimensions under the Gaussian noise assumption. We give the exact law of the sequence of knots conditional on the sequence of variables entering the model, i.e., the post-selection law of the knots of the LAR. Based on this result, we prove an exact of the False Discovery Rate (FDR) in the orthogonal design case and an exact control of the existence of false negatives in the general design case. First, we build a sequence of testing procedures on the variables entering the model and we give an exact control of the FDR in the orthogonal design case when the noise level can be unknown. Second, we introduce a new exact testing procedure on the existence of false negatives when the noise level can be unknown. This testing procedure can be deployed after any support selection procedure that will produce an estimation of the support (i.e., the indexes of nonzero coefficients) for any designs. The type~$I$ error of the test can be exactly controlled as long as the selection procedure follows some elementary hypotheses, referred to as admissible selection procedures. These support selection procedures are such that the estimation of the support is given by the $k$ first variables entering the model where the random variable $k$ is a stopping time. Monte-Carlo simulations and a real data experiment are provided to illustrate our results.

Published
2019

44. Metric completion of $Diff([0,1])$ with the $H1$ right-invariant metric

Author

Di Marino, Simone, Natale, Andrea, Tahraoui, Rabah, Vialard, François-Xavier, INDAM Unit [Roma], Università degli Studi di Brescia [Brescia], Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Università degli Studi di Brescia = University of Brescia (UniBs), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Mathematics - Analysis of PDEs, Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Analysis of PDEs (math.AP)
Abstract

We consider the group of smooth increasing diffeomorphisms Diff on the unit interval endowed with the right-invariant $H^1$ metric. We compute the metric completion of this space which appears to be the space of increasing maps of the unit interval with boundary conditions at $0$ and $1$. We compute the lower-semicontinuous envelope associated with the length minimizing geodesic variational problem. We discuss the Eulerian and Lagrangian formulation of this relaxation and we show that smooth solutions of the EPDiff equation are length minimizing for short times.

Published
2019

45. Embedding Camassa-Holm equations in incompressible Euler

Author

Andrea Natale, François-Xavier Vialard, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
Mathematics - Differential Geometry, Control and Optimization, 01 natural sciences, Physics::Fluid Dynamics, symbols.namesake, Mathematics - Analysis of PDEs, Incompressible Euler equation, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], 0101 mathematics, Camassa-Holm equation, Mathematics, Camassa–Holm equation, Applied Mathematics, 010102 general mathematics, Mathematical analysis, Riemannian manifold, Manifold, Euler equations, 010101 applied mathematics, Differential Geometry (math.DG), Mechanics of Materials, [MATH.MATH-DG]Mathematics [math]/Differential Geometry [math.DG], Metric (mathematics), Compressibility, symbols, Euler's formula, Embedding, Geometry and Topology, Mathematics::Differential Geometry, Eisenhart lift, Analysis of PDEs (math.AP)
Abstract

International audience; In this article, we show how to embed the so-called CH2 equations into the geodesic flow of the Hdiv metric in 2D, which, itself, can be embedded in the incompressible Euler equation of a non compact Riemannian manifold. The method consists in embedding the incompressible Euler equation with a potential term coming from classical mechanics into incompressible Euler of a manifold and seeing the CH2 equation as a particular case of such fluid dynamic equation.

Published
2019

46. Sample Complexity of Sinkhorn divergences

Author

Genevay, Aude, Chizat, L��naic, Bach, Francis, Cuturi, Marco, Peyr��, Gabriel, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Graduate School of Informatics [Kyoto], Kyoto University, Département de Mathématiques et Applications - ENS Paris (DMA), Kamalika Chaudhuri, Masashi Sugiyama, Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Kyoto University [Kyoto], Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris)

Subjects
[INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, FOS: Mathematics, [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT], Mathematics - Statistics Theory, Statistics Theory (math.ST), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience; Optimal transport (OT) and maximum mean discrepancies (MMD) are now routinely used in machine learning to compare probability measures. We focus in this paper on \emph{Sinkhorn divergences} (SDs), a regularized variant of OT distances which can interpolate, depending on the regularization strength $\varepsilon$, between OT ($\varepsilon=0$) and MMD ($\varepsilon=\infty$). Although the tradeoff induced by that regularization is now well understood computationally (OT, SDs and MMD require respectively $O(n^3\log n)$, $O(n^2)$ and $n^2$ operations given a sample size $n$), much less is known in terms of their \emph{sample complexity}, namely the gap between these quantities, when evaluated using finite samples \emph{vs.} their respective densities. Indeed, while the sample complexity of OT and MMD stand at two extremes, $1/n^{1/d}$ for OT in dimension $d$ and $1/\sqrt{n}$ for MMD, that for SDs has only been studied empirically. In this paper, we \emph{(i)} derive a bound on the approximation error made with SDs when approximating OT as a function of the regularizer $\varepsilon$, \emph{(ii)} prove that the optimizers of regularized OT are bounded in a Sobolev (RKHS) ball independent of the two measures and \emph{(iii)} provide the first sample complexity bound for SDs, obtained,by reformulating SDs as a maximization problem in a RKHS. We thus obtain a scaling in $1/\sqrt{n}$ (as in MMD), with a constant that depends however on $\varepsilon$, making the bridge between OT and MMD complete.

Published
2019

47. Régularisation Entropique du Transport Optimal pour le Machine Learning

Author

Genevay, Aude, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Département de Mathématiques et Applications - ENS Paris (DMA), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), PSL University, Gabriel Peyré (gabriel.peyre@ceremade.dauphine.fr), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, and Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
Transport optimal, Apprentissage statistique, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Machine learning, Optimal transport, [MATH]Mathematics [math], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

This thesis proposes theoretical and numerical contributions to use Entropy-regularized Optimal Transport (EOT) for machine learning. We introduce Sinkhorn Divergences (SD), a class of discrepancies between probability measures based on EOT which interpolates between two other well-known discrepancies: Optimal Transport (OT) and Maximum Mean Discrepancies (MMD). We develop an efficient numerical method to use SD for density fitting tasks, showing that a suitable choice of regularization can improve performance over existing methods. We derive a sample complexity theorem for SD which proves that choosing a large enough regularization parameter allows to break the curse of dimensionality from OT, and recover asymptotic rates similar to MMD. We propose and analyze stochastic optimization solvers for EOT, which yield online methods that can cope with arbitrary measures and are well suited to large scale problems, contrarily to existing discrete batch solvers.; Le Transport Optimal régularisé par l’Entropie (TOE) permet de définir les Divergences de Sinkhorn (DS), une nouvelle classe de distance entre mesures de probabilités basées sur le TOE. Celles-ci permettent d’interpoler entre deux autres dis- tances connues: le Transport Optimal (TO) et l’Ecart Moyen Maxi- mal (EMM). Les DS peuvent être utilisées pour apprendre des modèles probabilistes avec de meilleures performances que les algorithmes existants pour une régularisation adéquate. Ceci est justifié par un théorème sur l’approximation des SD par des échantillons, prouvant qu’une régularisation suffisante per- met de se débarrasser de la malédiction de la dimension du TO, et l’on retrouve à l’infini le taux de convergence des EMM. Enfin, nous présentons de nouveaux algorithmes de résolution pour le TOE basés sur l’optimisation stochastique ‘en-ligne’ qui, contrairement à l’état de l’art, ne se restreignent pas aux mesures discrètes et s’adaptent bien aux problèmes de grande dimension.

Published
2019

48. A fractal shape optimization problem in branched transport

Author

Filippo Santambrogio, Paul Pegon, Qinglan Xia, Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Mathematics [Univ California Davis] (MATH - UC Davis), University of California [Davis] (UC Davis), University of California (UC)-University of California (UC), ANR-12-BS01-0014,GEOMETRYA,Théorie géométrique de la mesure et applications(2012), ANR-18-LCV3-0003,MACRO,Maîtrise des Contraintes dans les Roulements(2018), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Department of Mathematics [Davis], and University of California-University of California

Subjects
Unit sphere, Pure mathematics, Non-smooth optimization, 2010 Mathematics Subject Classification: 49Q10, 49N60, 65K10, 28A80, General Mathematics, Phase-field approximation, Boundary (topology), [MATH.MATH-CA]Mathematics [math]/Classical Analysis and ODEs [math.CA], 01 natural sciences, Upper and lower bounds, Landscape function, Fractal, Branched transport, Classical Analysis and ODEs (math.CA), FOS: Mathematics, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Conjecture, Applied Mathematics, 010102 general mathematics, Minkowski–Bouligand dimension, Function (mathematics), 010101 applied mathematics, Morrey-Campanato spaces, Optimization and Control (math.OC), Mathematics - Classical Analysis and ODEs, Exponent, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Fractal dimension
Abstract

We investigate the following question: what is the set of unit volume which can be best irrigated starting from a single source at the origin, in the sense of branched transport? We may formulate this question as a shape optimization problem and prove existence of solutions, which can be considered as a sort of “unit ball” for branched transport. We establish some elementary properties of optimizers and describe these optimal sets A as sublevel sets of a so-called landscape function which is now classical in branched transport. We prove β-Holder regularity of the landscape function, allowing us to get an upper bound on the Minkowski dimension of the boundary: dim ‾ M ∂ A ≤ d − β (where β : = d ( α − ( 1 − 1 / d ) ) ∈ ( 0 , 1 ) is a relevant exponent in branched transport, associated with the exponent α > 1 − 1 / d appearing in the cost). We are not able to prove the lower bound, but we conjecture that ∂A is of non-integer dimension d − β . Finally, we make an attempt to compute numerically an optimal shape, using an adaptation of the phase-field approximation of branched transport introduced some years ago by Oudet and the second author.

Published
2019

49. Sparse analysis for mesoscale convective systems tracking

Author

Jean-Baptiste Courbot, Bernard Legras, Vincent Duval, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Météorologie Dynamique (UMR 8539) (LMD), Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-École des Ponts ParisTech (ENPC)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Département des Géosciences - ENS Paris, École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Institut de Recherche en Informatique Mathématiques Automatique Signal (IRIMAS), Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL), Sorbonne Université (SU), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)

Subjects
Convection, Computer science, Mesoscale meteorology, Cloud computing, 02 engineering and technology, Tracking (particle physics), Image (mathematics), gridless sparse analysis, Satellite image, 0202 electrical engineering, electronic engineering, information engineering, Computer vision, Surface brightness, Electrical and Electronic Engineering, Sparse image analysis, [SDU.OCEAN]Sciences of the Universe [physics]/Ocean, Atmosphere, Index Terms-Shape tracking, business.industry, 020206 networking & telecommunications, Remote sensing image processing, Shape tracking, Mesoscale Convective System tracking, Remote Sensing Image processing, Signal Processing, 020201 artificial intelligence & image processing, Mesoscale Convective Sys- tem tracking, Computer Vision and Pattern Recognition, Artificial intelligence, business, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Software
Abstract

International audience; In this paper, we study the tracking of de-formable shapes in sequences of images. Our target application is the tracking of clouds in satellite image. We propose to use a recent state-of-the-art method for off-the-grid sparse analysis to describe clouds in image as mixtures of 2D atoms. Then, we introduce an algorithm to handle the tracking with its specificities: apparition or disappearance of objects, merging, and splitting. This method provides similar numerical outputs as the recent state-of-the-art alternatives, while being more flexible, and providing additional information on, e.g., cloud surface brightness.

Published
2019

50. A variational finite volume scheme for Wasserstein gradient flows

Author

Gabriele Todeschi, Thomas Gallouët, Clément Cancès, Reliable numerical approximations of dissipative systems (RAPSODI ), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Clément Cancès acknowledges the support of the Labex CEMPI (ANR-11-LABX-0007-01). Gabriele Todeschi acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 754362., ANR-11-LABX-0007,CEMPI,Centre Européen pour les Mathématiques, la Physique et leurs Interactions(2011), European Project: 754362,MathInParis(2017), Laboratoire Paul Painlevé - UMR 8524 (LPP), Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Inria Lille - Nord Europe, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
Finite volume method, Spacetime, Discretization, Continuous modelling, Applied Mathematics, Numerical analysis, 010103 numerical & computational mathematics, Numerical Analysis (math.NA), Space (mathematics), 01 natural sciences, 010101 applied mathematics, Computational Mathematics, 65M08, 65M12, 49M29, 35K65, Linearization, Convergence (routing), FOS: Mathematics, Applied mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Mathematics - Numerical Analysis, 0101 mathematics, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Mathematics
Abstract

International audience; We propose a variational finite volume scheme to approximate the solutions to Wasserstein gradient flows. The time discretization is based on an implicit linearization of the Wasserstein distance expressed thanks to Benamou-Brenier formula, whereas space discretization relies on upstream mobility two-point flux approximation finite volumes. Our scheme is based on a first discretize then optimize approach in order to preserve the variational structure of the continuous model at the discrete level. Our scheme can be applied to a wide range of energies, guarantees non-negativity of the discrete solutions as well as decay of the energy. We show that our scheme admits a unique solution whatever the convex energy involved in the continuous problem , and we prove its convergence in the case of the linear Fokker-Planck equation with positive initial density. Numerical illustrations show that it is first order accurate in both time and space, and robust with respect to both the energy and the initial profile.

Published
2019
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results