131,227 research outputs found
Manifold learning in Wasserstein space
No full textThis paper aims at building the theoretical foundations for manifold learning algorithms in the space of absolutely continuous probability measures on a compact and convex subset of , metrized with the Wasserstein-2 distance . We begin by introducing a natural construction of submanifolds of probability measures equipped with metric , the geodesic restriction of to . In contrast to other constructions, these submanifolds are not necessarily flat, but still allow for local linearizations in a similar fashion to Riemannian submanifolds of . We then show how the latent manifold structure of can be learned from samples of and pairwise extrinsic Wasserstein distances only. In particular, we show that the metric space can be asymptotically recovered in the sense of Gromov--Wasserstein from a graph with nodes and edge weights . In addition, we demonstrate how the tangent space at a sample can be asymptotically recovered via spectral analysis of a suitable "covariance operator" using optimal transport maps from to sufficiently close and diverse samples . The paper closes with some explicit constructions of submanifolds and numerical examples on the recovery of tangent spaces through spectral analysis
Problèmes d'interaction discret-continu et distances de Wasserstein
No full textOn étudie dans ce manuscrit plusieurs problèmes d'approximation à l'aide des outils de la théorie du transport optimal. Les distances de Wasserstein fournissent des bornes d'erreur pour l'approximation particulaire des solutions de certaines équations aux dérivées partielles.
Elles jouent également le rôle de mesures de distorsion naturelles dans les problèmes de quantification et de partitionnement ("clustering"). Un problème associé à ces questions est d'étudier la vitesse de convergence dans la loi des grands nombres empirique pour cette distorsion. La première partie de cette thèse établit des bornes non-asymptotiques, en particulier dans des espaces de Banach de dimension infinie, ainsi que dans les cas où les observations sont non-indépendantes. La seconde partie est consacrée à l'étude de deux modèles issus de la modélisation des déplacements de populations d'animaux. On introduit un nouveau modèle individu-centré de formation de pistes de fourmis, que l'on étudie expérimentalement à travers des simulations numériques et une représentation en terme d'équations cinétiques. On étudie également une variante du modèle de Cucker-Smale de mouvement d'une
nuée d'oiseaux : on montre le caractère bien posé de l'équation de transport de type Vlasov associée, et on établit des résultats sur le comportement en temps long de cette équation. Enfin, dans une troisième partie, on étudie certaines applications statistiques de la notion de barycentre dans l'espace des mesures de probabilités muni de la distance de Wasserstein, récemment introduite par M. Agueh et G. Carlier.We study several problems of approximation using tools from Optimal Transportation theory. The family of Wasserstein metrics are used to provide error bounds for particular approximation of some Partial Differential Equations. They also come into play as natural measures of distorsion for quantization and clustering problems. A problem related to these questions is to estimate the speed of convergence in the empirical law of large numbers for these distorsions. The first part of this thesis provides non-asymptotic bounds, notably in infinite-dimensional Banach spaces, as well as in cases where independence is removed. The second part is dedicated to the study of two models from the modelling of animal displacement. A new individual-based model for ant trail formation is introduced, and studied through numerical simulations and kinetic formulation. We also study a variant of the Cucker-Smale model of bird flock motion : we establish well-posedness of the associated Vlasov-type transport equation as well as long-time behaviour results. In a third part, we study some statistical applications of the notion of barycenter in Wasserstein space recently introduced by M.Agueh and G.Carlier
Triangle inequalities of quantum Wasserstein distances on noncommutative tori
No full textIn 2022, Golse and Paul defined a pseudometric for quantum optimal transport that extends the classical Wasserstein distance. They proved that the pseudometric satisfies the triangle inequality in certain cases. This thesis reviews their proof in the case where the middle point is a classical density. Motivated by that proof, we formulate the optimal transport problem and propose the quantum Wasserstein distance on the noncommutative 2-torus. This thesis also proves that the proposed quantum Wasserstein distance satisfies the triangle inequality in the case where the middle point is a classical density on the 2-torus.Applied Mathematic
Statistical inference for Bures-Wasserstein barycenters
No full textIn this work we introduce the concept of Bures--Wasserstein barycenter , that is essentially a Fréchet mean of some distribution supported on a subspace of positive semi-definite -dimensional Hermitian operators . We allow a barycenter to be constrained to some affine subspace of , and we provide conditions ensuring its existence and uniqueness. We also investigate convergence and concentration properties of an empirical counterpart of in both Frobenius norm and Bures--Wasserstein distance, and explain, how the obtained results are connected to optimal transportation theory and can be applied to statistical inference in quantum mechanics
Maximal Martingale Wasserstein Inequality
No full textInternational audienceIn this note, we complete the analysis of the Martingale Wasserstein Inequality started in [5] by checking that this inequality fails in dimension d ≥ 2 when the integrability parameter ρ belongs to [1, 2) while a stronger Maximal Martingale Wasserstein Inequality holds whatever the dimension d when ρ ≥ 2
Computing Kantorovich-Wasserstein Distances on d-dimensional histograms using (d + 1)-partite graphs
No full textThis paper presents a novel method to compute the exact Kantorovich-Wasserstein distance between a pair of d-dimensional histograms having n bins each. We prove that this problem is equivalent to an uncapacitated minimum cost flow problem on a (d + 1)-partite graph with (d + 1)n nodes and dn d+1 d arcs, whenever the cost is separable along the principal d-dimensional directions. We show numerically the benefits of our approach by computing the Kantorovich-Wasserstein distance of order 2 among two sets of instances: gray scale images and d-dimensional bio medical histograms. On these types of instances, our approach is competitive with state-of-the-art optimal transport algorithms
Computing Kantorovich-Wasserstein Distances on d-dimensional histograms using (d+1)-partite graphs
No full textThis paper presents a novel method to compute the exact Kantorovich-Wasserstein distance between a pair of d-dimensional histograms having n bins each. We prove that this problem is equivalent to an uncapacitated minimum cost flow problem on a (d + 1)-partite graph with (d + 1)n nodes and dn d+1/d arcs, whenever the cost is separable along the principal d-dimensional directions. We show numerically the benefits of our approach by computing the Kantorovich-Wasserstein distance of order 2 among two sets of instances: gray scale images and d-dimensional bio medical histograms. On these types of instances, our approach is competitive with state-of-the-art optimal transport algorithms
Stein's method and Poisson process approximation for a class of Wasserstein metrics
No full textBased on Stein\’s method, we derive upper bounds for Poisson process approximation in the L1-Wasserstein metric d (p) 2 , which is based on a slightly adapted Lp-Wasserstein metric between point measures. For the case p = 1, this construction yields the metric d2 introduced in [Barbour and Brown Stochastic Process. Appl. 43 (1992) 9–31], for which Poisson process approximation is well studied in the literature.We demonstrate the usefulness of the extension to general p by showing that d (p) 2 -bounds control differences between expectations of certain pth order average statistics of point processes. To illustrate the bounds obtained for Poisson process approximation, we consider the structure of 2-runs and the hard core model as concrete examples
Mirror and Preconditioned Gradient Descent in Wasserstein Space
No full textInternational audienceAs the problem of minimizing functionals on the Wasserstein space encompasses many applications in machine learning, different optimization algorithms on have received their counterpart analog on the Wasserstein space. We focus here on lifting two explicit algorithms: mirror descent and preconditioned gradient descent. These algorithms have been introduced to better capture the geometry of the function to minimize and are provably convergent under appropriate (namely relative) smoothness and convexity conditions. Adapting these notions to the Wasserstein space, we prove guarantees of convergence of some Wasserstein-gradient-based discrete-time schemes for new pairings of objective functionals and regularizers. The difficulty here is to carefully select along which curves the functionals should be smooth and convex. We illustrate the advantages of adapting the geometry induced by the regularizer on ill-conditioned optimization tasks, and showcase the improvement of choosing different discrepancies and geometries in a computational biology task of aligning single-cells
Wasserstein medians: robustness, PDE characterization and numerics
No full text38 pages, 6 figuresWe investigate the notion of Wasserstein median as an alternative to the Wasserstein barycenter, which has become popular but may be sensitive to outliers. In terms of robustness to corrupted data, we indeed show that Wasserstein medians have a breakdown point of approximately 1 2. We give explicit constructions of Wasserstein medians in dimension one which enable us to obtain L p estimates (which do not hold in higher dimensions). We also address dual and multimarginal reformulations. In convex subsets of R d , we connect Wasserstein medians to a minimal (multi) flow problem à la Beckmann and a system of PDEs of Monge-Kantorovich-type, for which we propose a p-Laplacian approximation. Our analysis eventually leads to a new numerical method to compute Wasserstein medians, which is based on a Douglas-Rachford scheme applied to the minimal flow formulation of the problem
- …
