Author: "Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL"' showing total 3,931 results

Start Over Author "Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL"

3,931 results on '"Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL"'

1. 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

2. 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

3. Model-based Clustering with Missing Not At Random Data

Author: Sportisse, Aude, Biernacki, Christophe, Boyer, Claire, Josse, Julie, Marbac Lourdelle, Matthieu, Celeux, Gilles, Laporte, Fabien, Université Côte d'Azur (UCA), Modèles et algorithmes pour l’intelligence artificielle (MAASAI), Inria Sophia Antipolis - Méditerranée (CRISAM), 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é (JAD), 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), Université de Rennes (UNIV-RENNES), Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz] (ENSAI), Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Economie et Statistique [Bruz] (CREST), Université Lille Nord (France), MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé - UMR 8524 (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), Sorbonne Université (SU), Laboratoire de Probabilités, Statistique et Modélisation (LPSM (UMR_8001)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), 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), Institut Desbrest de santé publique (IDESP), Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM), Médecine de précision par intégration de données et inférence causale (PREMEDICAL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Desbrest de santé publique (IDESP), Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris-Saclay, Nantes Université (Nantes Univ), Institut du Thorax [Nantes], INSERM U649, Nantes, Institut National de la Santé et de la Recherche Médicale (INSERM), ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), ANR-16-IDEX-0006,MUSE,MUSE(2016), Inria Lille - Nord Europe, Université Catholique de l'Ouest (UCO), 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é de Rennes (UR), Laboratoire Paul Painlevé (LPP), Statistique mathématique et apprentissage (CELESTE), 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), 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), 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), 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), Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Laboratoire de Probabilités, Statistiques et Modélisations (LPSM (UMR_8001)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPC), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Missing Not At Random (MNAR) Data, Model-based Clustering, Machine Learning (stat.ML), Identifiability, EM and Stochastic EM Algorithms, Machine Learning (cs.LG), Medical Data
Abstract: In recent decades, technological advances have made it possible to collect large data sets. In this context, the model-based clustering is a very popular, flexible and interpretable methodology for data exploration in a well-defined statistical framework. One of the ironies of the increase of large datasets is that missing values are more frequent. However, traditional ways (as discarding observations with missing values or imputation methods) are not designed for the clustering purpose. In addition, they rarely apply to the general case, though frequent in practice, of Missing Not At Random (MNAR) values, i.e. when the missingness depends on the unobserved data values and possibly on the observed data values. The goal of this paper is to propose a novel approach by embedding MNAR data directly within model-based clustering algorithms. We introduce a selection model for the joint distribution of data and missing-data indicator. It corresponds to a mixture model for the data distribution and a general MNAR model for the missing-data mechanism, which may depend on the underlying classes (unknown) and/or the values of the missing variables themselves. A large set of meaningful MNAR sub-models is derived and the identifiability of the parameters is studied for each of the sub-models, which is usually a key issue for any MNAR proposals. The EM and Stochastic EM algorithms are considered for estimation. Finally, we perform empirical evaluations for the proposed submodels on synthetic data and we illustrate the relevance of our method on a medical register, the TraumaBase ® dataset.
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 Classiﬁcation: 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. Convex transport potential selection with semi-dual criterion

Author: Vacher, Adrien, Vialard, François-Xavier, 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), 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é Gustave Eiffel, 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 École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel
Subjects: model selection, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Semi-dual, Optimal transport
Abstract: Over the past few years, numerous computational models have been developed to solve Optimal Transport (OT) in a stochastic setting, where distributions are represented by samples. In such situations, the goal is to find a transport map that has good generalization properties on unseen data, ideally the closest map to the ground truth, unknown in practical settings. However, in the absence of ground truth, no quantitative criterion has been put forward to measure its generalization performance although it is crucial for model selection. We propose to leverage the Brenier formulation of OT to perform this task. Theoretically, we show that this formulation guarantees that, up to a distortion parameter that depends on the smoothness/strong convexity and a statistical deviation term, the selected map achieves the lowest quadratic error to the ground truth. This criterion, estimated via convex optimization, enables parameter and model selection among entropic regularization of OT, input convex neural networks and smooth and strongly convex nearest-Brenier (SSNB) models. Last, we make an experiment questioning the use of OT in Domain-Adaptation. Thanks to the criterion, we can identify the potential that is closest to the true OT map between the source and the target and we observe that this selected potential is not the one that performs best for the downstream transfer classification task.
Published: 2021

11. Near-optimal estimation of smooth transport maps with kernel sums-of-squares

Author: Muzellec, Boris, Vacher, Adrien, Bach, Francis, Vialard, François-Xavier, Rudi, Alessandro, Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (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), 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), Université Paris sciences et lettres (PSL), Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Université Gustave Eiffel, 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), ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), É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 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 Département d'informatique de l'École normale supérieure (DI-ENS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, Machine Learning (stat.ML), Mathematics - Statistics Theory, Statistics Theory (math.ST), Machine Learning (cs.LG)
Abstract: It was recently shown that under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. However, rather than the distance itself, the object of interest for applications such as generative modeling is the underlying optimal transport map. Hence, computational and statistical guarantees need to be obtained for the estimated maps themselves. In this paper, we propose the first tractable algorithm for which the statistical $L^2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation. Our method is based on solving the semi-dual formulation of optimal transport with an infinite-dimensional sum-of-squares reformulation, and leads to an algorithm which has dimension-free polynomial rates in the number of samples, with potentially exponentially dimension-dependent constants.
Published: 2021

12. 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

13. 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 reﬂector 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 reﬂector surface mapping a prescribed source distribution of light to a prescribed far ﬁeld distribution, for a ﬁnite light source. When the ﬁnite 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 ﬁnite 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 reﬂec-tor and the reﬂection map. Under this parameterization we can construct a smooth loss/misﬁt function to optimize for the best solution in this class of reﬂectors. 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

14. 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

15. A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation

Author: Vacher, Adrien, Muzellec, Boris, Rudi, Alessandro, Bach, Francis, Vialard, Francois-Xavier, Université Gustave Eiffel, Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, 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), 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), Université Paris sciences et lettres (PSL), This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the 'Investissements d’avenir' program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We also acknowledge support from the European Research Council (grants SEQUOIA 724063 and REAL 947908), and Région Ile-de-France., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), European Project: 724063,ERC-2016-COG,SEQUOIA(2017), European Project: 947908,REAL, 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), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris
Subjects: [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Optimization and Control (math.OC), [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, Mathematics - Statistics Theory, 62G05, Statistics Theory (math.ST), Mathematics - Optimization and Control
Abstract: It is well-known that plug-in statistical estimation of optimal transport suffers from the curse of dimensionality. Despite recent efforts to improve the rate of estimation with the smoothness of the problem, the computational complexity of these recently proposed methods still degrades exponentially with the dimension. In this paper, thanks to an infinite-dimensional sum-of-squares representation, we derive a statistical estimator of smooth optimal transport which achieves a precision $\varepsilon$ from $\tilde{O}(\varepsilon^{-2})$ independent and identically distributed samples from the distributions, for a computational cost of $\tilde{O}(\varepsilon^{-4})$ when the smoothness increases, hence yielding dimension-free statistical and computational rates, with potentially exponentially dimension-dependent constants., Comment: 30 pages
Published: 2021

16. 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

17. 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

18. 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

19. 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

20. 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

21. 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

22. Is the Covid equity bubble rational? A machine learning answer

Author: Jacques Ohana, Jean, Benhamou, Eric, Saltiel, David, Guez, Beatrice, Machine Intelligence and Learning Systems (MILES), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), 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, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [QFIN.GN]Quantitative Finance [q-fin]/General Finance [q-fin.GN], [SHS.STAT]Humanities and Social Sciences/Methods and statistics, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], [SCCO.COMP]Cognitive science/Computer science, [QFIN.CP]Quantitative Finance [q-fin]/Computational Finance [q-fin.CP], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: Is the Covid Equity bubble rational? In 2020, stock prices ballooned with S&P 500 gaining 16%, and the tech-heavy Nasdaq soaring to 43%, while fundamentals deteriorated with decreasing GDP forecasts, shrinking sales and revenues estimates and higher government deficits. To answer this fundamental question, with little bias as possible, we explore a gradient boosting decision trees (GBDT) approach that enables us to crunch numerous variables and let the data speak. We define a crisis regime to identify specific downturns in stock markets and normal rising equity markets. We test our approach and report improved accuracy of GBDT over other ML methods. Thanks to Shapley values, we are able to identify most important features, making this current work innovative and a suitable answer to the justification of current equity level.
Published: 2021

23. Computation of the marginal contribution of Sharpe ratio and other performance ratios

Author: Eric Benhamou, Beatrice Guez, Machine Intelligence and Learning Systems (MILES), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), 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), 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: Sharpe, Homogeneous function, [SHS]Humanities and Social Sciences, symbols.namesake, Marginal contribution, Treynor ratio, 0502 economics and business, Econometrics, JEL: G - Financial Economics/G.G1 - General Financial Markets/G.G1.G11 - Portfolio Choice • Investment Decisions, Asset (economics), 050207 economics, [MATH]Mathematics [math], Linear combination, Modern portfolio theory, Mathematics, 050208 finance, portfolio analysis, Sharpe ratio, 05 social sciences, JEL: C - Mathematical and Quantitative Methods/C.C1 - Econometric and Statistical Methods and Methodology: General/C.C1.C12 - Hypothesis Testing: General, recovery and incremental Sharpe ratio, [SHS.ECO]Humanities and Social Sciences/Economics and Finance, Euler's formula, symbols, Portfolio, Treynor
Abstract: Computing incremental contribution of performance ratios like Sharpe, Treynor, Calmar or Sterling ratios is of paramount importance for asset managers. Leveraging Euler's homogeneous function theorem, we are able to prove that these performance ratios are indeed a linear combination of individual modified performance ratios. This allows not only deriving a condition for a new asset to provide incremental performance for the portfolio but also to identify the key drivers of these performance ratios. We provide various numerical examples of this performance ratio decomposition.
Published: 2021

24. 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

25. 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

26. '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

27. 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

28. 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

29. Positive Semidefinite Relaxations for Imaging Science

Author: Catala, Paul, Département de Mathématiques et Applications - ENS Paris (DMA), Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), 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), 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), Ecole Normale Supérieure, Gabriel PEYRE, and Vincent DUVAL
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

30. 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

31. 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

32. Audit de management des connaissances à la DGA

Author: Dudezert, Aurélie, Laval, Florence, Janand, Anne, Laniray, Pierre, Réseaux Innovation Territoires et Mondialisation (RITM), Université Paris-Sud - Paris 11 (UP11), CEntre de REcherche en GEstion - EA 1722 (CEREGE), Institut d'Administration des Entreprises (IAE) - Poitiers (IAE Poitiers), Université de Poitiers-Université de Poitiers-Université de Poitiers-Université de La Rochelle (ULR), Dauphine Recherches en Management - MLAB (DRM - MLAB), Dauphine Recherches en Management (DRM), 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), DGA, 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: [SHS]Humanities and Social Sciences
Published: 2020

33. 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

34. 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

35. 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 ﬁnite-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 ﬂexible enough to adapt to partial participation models as well as to the case of type-dependent budget constraints.
Published: 2020

36. 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

37. 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 classiﬁcations: 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

38. 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

39. 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

40. 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

41. 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

42. 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

43. 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

44. 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

45. 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

46. 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

47. 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

48. 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

49. 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

50. Illiquidité et contexte de crise des marchés financiers - Un risque sous-estimé ?

Author: Astolfi, Pierre, Thauvron, Arnaud, Desban, Marc, Lecarpentier-Moyal, Sylvie, DRM-Finance, Dauphine Recherches en Management (DRM), 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), Institut de Recherche en Gestion (IRG), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Université Paris-Est Marne-la-Vallée (UPEM), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris-Est Marne-la-Vallée (UPEM)-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12), and DESBAN, Marc
Subjects: [QFIN.ST] Quantitative Finance [q-fin]/Statistical Finance [q-fin.ST], [QFIN.GN] Quantitative Finance [q-fin]/General Finance [q-fin.GN], [QFIN.GN]Quantitative Finance [q-fin]/General Finance [q-fin.GN], [QFIN.PR]Quantitative Finance [q-fin]/Pricing of Securities [q-fin.PR], [QFIN.CP] Quantitative Finance [q-fin]/Computational Finance [q-fin.CP], IRG_AXE1, [QFIN.PR] Quantitative Finance [q-fin]/Pricing of Securities [q-fin.PR], [QFIN.ST]Quantitative Finance [q-fin]/Statistical Finance [q-fin.ST], [QFIN.CP]Quantitative Finance [q-fin]/Computational Finance [q-fin.CP], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2019

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

3,931 results on '"Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources