In this thesis, results will be presented that pertain to the global regularity of solutions to boundary value problems having the general form \begin{align} F\left[D^2u-A(\,\cdot\,,u,Du)\right] &= B(\,\cdot\,,u,Du),\quad\text{in}\ \Omega^-,\notag\\ T_u(\Omega^-) &= \Omega^+, \end{align} where $A$, $B$, $T_u$ are all prescribed; and $\Omega^-$ along with $\Omega^+$ are bounded in $\mathbb{R}^n$, smooth and satisfying notions of c-convexity and c^*-convexity relative to one another (see [MTW05] for definitions). In particular, the case where $F$ is a quotient of symmetric functions of the eigenvalues of its argument matrix will be investigated. Ultimately, analogies to the global regularity result presented in [TW06] for the Optimal Transportation Problem to this new fully-nonlinear elliptic boundary value problem will be presented and proven. It will also be shown that the A3w condition (first presented in [MTW05]) is also necessary for global regularity in the case of (1). The core part of this research lies in proving various a priori estimates so that a method of continuity argument can be applied to get the existence of globally smooth solutions. The a priori estimates vary from those presented in [TW06], due to the structure of F, introducing some complications that are not present in the Optimal Transportation case.¶ In the final chapter of this thesis, the A3 condition will be reformulated and analysed on round spheres. The example cost-functions subsequently analysed have already been studied in the Euclidean case within [MTW05] and [TW06]. In this research, a stereographic projection is utilised to reformulate the A3 condition on round spheres for a general class of cost-functions, which are general functions of the geodesic distance as defined relative to the underlying round sphere. With this general expression, the A3 condition can be readily verified for a large class of cost-functions that depend on the metrics of round spheres, which is tantamount (combined with some geometric assumptions on the source and target domains) to the classical regularity for solutions of the Optimal Transportation Problem on round spheres.

Apresentamos o problema do transporte ótimo de Monge-Kantorovich com duas medidas de probabilidade conhecidas e que possuem suporte em um conjunto de cardinalidade finita. O objetivo é determinar condições que permitam construir um acoplamento destas medidas que minimiza o valor esperado de uma função de custo conhecida e que assume valor nulo apenas nos elementos da diagonal. Apresentamos também um resultado relacionado com a solução do problema de Monge-Kantorovich em espaços produto finitos quando conhecemos soluções para o problema nos espaços marginais. / We present the Monge-Kantorovich optimal problem with two known probability measures on a finite set. The objective is to obtain conditions that allow us to build a coupling of these measures that minimizes the expected value of a cost function that is known and is zero only on the diagonal elements. We also present a result that is related with the solution of the Monge-Kantorovich problem in finite product spaces in the case that solutions to the problem in the marginal spaces are known.

abstract: This thesis introduces new techniques for clustering distributional data according to their geometric similarities. This work builds upon the optimal transportation (OT) problem that seeks global minimum cost for matching distributional data and leverages the connection between OT and power diagrams to solve different clustering problems. The OT formulation is based on the variational principle to differentiate hard cluster assignments, which was missing in the literature. This thesis shows multiple techniques to regularize and generalize OT to cope with various tasks including clustering, aligning, and interpolating distributional data. It also discusses the connections of the new formulation to other OT and clustering formulations to better understand their gaps and the means to close them. Finally, this thesis demonstrates the advantages of the proposed OT techniques in solving machine learning problems and their downstream applications in computer graphics, computer vision, and image processing. / Dissertation/Thesis / Doctoral Dissertation Computer Engineering 2020

Cette thèse comprend deux parties indépendantes.Dans la première partie nous contribuons une nouvelle méthode qui, étant donnée un volume de tolérance, génère un maillage triangulaire surfacique garanti d’être dans le volume de tolérance, sans auto-intersection et topologiquement correct. Un algorithme flexible est conçu pour capturer la topologie et découvrir l’anisotropie dans le volume de tolérance dans le but de générer un maillage de faible complexité.Dans la seconde partie nous contribuons une nouvelle approche pour calculer une fonction de correspondance entre deux surfaces. Tandis que la plupart des approches précédentes procède par composition de correspondance avec un domaine simple planaire, nous calculons une fonction de correspondance en optimisant directement une fonction de sorte à minimiser la variance d’un plan de transport entre les surfaces / This thesis is divided into two independent parts.In the first part, we introduce a method that, given an input tolerance volume, generates a surface triangle mesh guaranteed to be within the tolerance, intersection free and topologically correct. A pliant meshing algorithm is used to capture the topology and discover the anisotropy in the input tolerance volume in order to generate a concise output. We first refine a 3D Delaunay triangulation over the tolerance volume while maintaining a piecewise-linear function on this triangulation, until an isosurface of this function matches the topology sought after. We then embed the isosurface into the 3D triangulation via mutual tessellation, and simplify it while preserving the topology. Our approach extends toDépôt de thèseDonnées complémentairessurfaces with boundaries and to non-manifold surfaces. We demonstrate the versatility and efficacy of our approach on a variety of data sets and tolerance volumes.In the second part we introduce a new approach for creating a homeomorphic map between two discrete surfaces. While most previous approaches compose maps over intermediate domains which result in suboptimal inter-surface mapping, we directly optimize a map by computing a variance-minimizing mass transport plan between two surfaces. This non-linear problem, which amounts to minimizing the Dirichlet energy of both the map and its inverse, is solved using two alternating convex optimization problems in a coarse-to-fine fashion. Computational efficiency is further improved through the use of Sinkhorn iterations (modified to handle minimal regularization and unbalanced transport plans) and diffusion distances. The resulting inter-surface mapping algorithm applies to arbitrary shapes robustly and efficiently, with little to no user interaction.

Dans cette thèse, nous nous intéressons aux équations des gaz sans pression avec contrainte de congestion qui soulèvent encore de nombreuses questions. La stratégie que nous proposons repose sur des précédents travaux sur le mouvement de foule dans le cadre de l'espace de Wasserstein, et sur un modèle granulaire avec des collisions inélastiques.Elle consiste en l'étude d'un schéma discrétisé en temps dont les suites doivent approcher les solutions de ces équations.Le schéma se présente de la manière suivante : à chaque pas de temps, le champ des vitesses est projeté sur un ensemble lui permettant d'éviter les croisements entre particules, la densité est ensuite déplacée selon le nouveau champ des vitesses, puis est projetée sur l'ensemble des densités admissibles (inférieures à une valeur seuil donnée).Enfin, le champ des vitesses est mis à jour en tenant compte du parcours effectué par les particules. En dimension 1, les solutions calculées par le schéma coïncident avec les solutions connues pour ce système. En dimension 2, les solutions calculées respectent les propriétés connues des solutions des équations de gaz sans pression avec contrainte de congestion. De plus, on retrouve des similarités entres ces solutions et celles du modèle granulaire microscopique dans des cas où elles sont comparables. Par la suite, la discrétisation en espace pose des problèmes et a nécessité l'élaboration d'un nouveau schéma de discrétisation du coût Wasserstein quadratique. Cette méthode que nous avons baptisée méthode du balayage transverse consiste à calculer le coût en utilisant les flux de masses provenant d'une certaine cellule et traversant les hyperplans définis par les interfaces entre les cellules. / In this thesis, we consider the pressureless Euler equations with a congestion constraint.This system still raises many open questions and aside from its one-dimensional version,very little is known. The strategy that we propose relies on previous works of crowd motion models withcongestion in the framework of the Wasserstein space, and on a microscopic granularmodel with inelastic collisions. It consists of the study of a time-splitting scheme. The first step is about the projection of the current velocity field on a set, avoiding the factthat trajectories do not cross during the time step. Then the scheme moves the density with the new velocity field. This intermediate density may violate the congestion constraint. The third step projects it on the set of admissible densities. Finally, the velocity field is updated taking into account the positions of physical particles during the scheme. In the one-dimensional case, solutions computed by the algorithm matchwith the ones that we know for these equations. In the two-dimensional case, computed solutions respect some properties that can be expected to be verified by the solutions to these equations. In addition, we notice some similarities between solutions computed by the scheme and the ones of the granular model with inelastic collisions. Later, this scheme is discretized with respect to the space variable in the purpose of numerical computations of solutions. The resulting algorithm uses a new method to discretize the Wasserstein cost. This method, called Transverse Sweeping Method consists in expressing the cost using the mass flow from any cell and crossing hyperplanes defined by interfaces between cells.

No description available.

In this thesis we prove several results on the structure of solutions to optimal transportation problems. The second chapter represents joint work with Robert McCann and Micah Warren; the main result is that, under a non-degeneracy condition on the cost function, the optimal is concentrated on a $n$-dimensional Lipschitz submanifold of the product space. As a consequence, we provide a simple, new proof that the optimal map satisfies a Jacobian equation almost everywhere. In the third chapter, we prove an analogous result for the multi-marginal optimal transportation problem; in this context, the dimension of the support of the solution depends on the signatures of a $2^{m-1}$ vertex convex polytope of semi-Riemannian metrics on the product space, induce by the cost function. In the fourth chapter, we identify sufficient conditions under which the solution to the multi-marginal problem is concentrated on the graph of a function over one of the marginals. In the fifth chapter, we investigate the regularity of the optimal map when the dimensions of the two spaces fail to coincide. We prove that a regularity theory can be developed only for very special cost functions, in which case a quotient construction can be used to reduce the problem to an optimal transport problem between spaces of equal dimension. The final chapter applies the results of chapter 5 to the principal-agent problem in mathematical economics when the space of types and the space of available goods differ. When the dimension of the space of types exceeds the dimension of the space of goods, we show if the problem can be formulated as a maximization over a convex set, a quotient procedure can reduce the problem to one where the two dimensions coincide. Analogous conditions are investigated when the dimension of the space of goods exceeds that of the space of types.

In this thesis we prove several results on the structure of solutions to optimal transportation problems. The second chapter represents joint work with Robert McCann and Micah Warren; the main result is that, under a non-degeneracy condition on the cost function, the optimal is concentrated on a $n$-dimensional Lipschitz submanifold of the product space. As a consequence, we provide a simple, new proof that the optimal map satisfies a Jacobian equation almost everywhere. In the third chapter, we prove an analogous result for the multi-marginal optimal transportation problem; in this context, the dimension of the support of the solution depends on the signatures of a $2^{m-1}$ vertex convex polytope of semi-Riemannian metrics on the product space, induce by the cost function. In the fourth chapter, we identify sufficient conditions under which the solution to the multi-marginal problem is concentrated on the graph of a function over one of the marginals. In the fifth chapter, we investigate the regularity of the optimal map when the dimensions of the two spaces fail to coincide. We prove that a regularity theory can be developed only for very special cost functions, in which case a quotient construction can be used to reduce the problem to an optimal transport problem between spaces of equal dimension. The final chapter applies the results of chapter 5 to the principal-agent problem in mathematical economics when the space of types and the space of available goods differ. When the dimension of the space of types exceeds the dimension of the space of goods, we show if the problem can be formulated as a maximization over a convex set, a quotient procedure can reduce the problem to one where the two dimensions coincide. Analogous conditions are investigated when the dimension of the space of goods exceeds that of the space of types.

Pour prédire l'évolution d'un système physique, nous avons besoin d'initialiser le modèle mathématique le représentant, donc d'estimer la valeur de l'état du système au temps initial. Cet état n'est généralement pas directement mesurable car souvent trop complexe. En revanche, nous disposons d'informations du système, prises à des temps différents, incomplètes, mais aussi entachées d'erreurs, telles des observations, de précédentes estimations, etc. Combiner ces différentes informations partielles et imparfaites pour estimer la valeur de l'état fait appel à des méthodes d'assimilation de données dont l'idée est de trouver un état initial proche de toutes les informations. Ces méthodes sont très utilisées en météorologie. Nous nous intéressons dans cette thèse à l'assimilation d'images, images qui sont de plus en plus utilisées en tant qu'observations. La spécificité de ces images est leur cohérence spatiale, l'oeil humain peut en effet percevoir des structures dans les images que les méthodes classiques d'assimilation ne considèrent généralement pas. Elles ne tiennent compte que des valeurs de chaque pixel, ce qui résulte dans certains cas à des problèmes d'amplitude dans l'état initial estimé. Pour résoudre ce problème, nous proposons de changer d'espace de représentation des données : nous plaçons les données dans un espace de Wasserstein où la position des différentes structures compte. Cet espace, équipé d'une distance de Wasserstein, est issue de la théorie du transport optimal et trouve beaucoup d'applications en imagerie notamment.Dans ce travail nous proposons une méthode d'assimilation variationnelle de données basée sur cette distance de Wasserstein. Nous la présentons ici, ainsi que les algorithmes numériques liés et des expériences montrant ses spécificités. Nous verrons dans les résultats comment elle permet de corriger ce qu'on appelle erreurs de position. / Forecasting of a physical system is computed by the help of a mathematical model. This model needs to be initialized by the state of the system at initial time. But this state is not directly measurable and data assimilation techniques are generally used to estimate it. They combine all sources of information such as observations (that may be sparse in time and space and potentially include errors), previous forecasts, the model equations and error statistics. The main idea of data assimilation techniques is to find an initial state accounting for the different sources of informations. Such techniques are widely used in meteorology, where data and particularly images are more and more numerous due to the increasing number of satellites and other sources of measurements. This, coupled with developments of meteorological models, have led to an ever-increasing quality of the forecast.Spatial consistency is one specificity of images. For example, human eyes are able to notice structures in an image. However, classical methods of data assimilation do not handle such structures because they take only into account the values of each pixel separately. In some cases it leads to a bad initial condition. To tackle this problem, we proposed to change the representation of an image: images are considered here as elements of the Wasserstein space endowed with the Wasserstein distance coming from the optimal transport theory. In this space, what matters is the positions of the different structures.This thesis presents a data assimilation technique based on this Wasserstein distance. This technique and its numerical procedure are first described, then experiments are carried out and results shown. In particularly, it appears that this technique was able to give an analysis of corrected position.

Orientadores: Lucas Catão de Freitas Ferreira, Marcelo da Silva Montenegro, José Antonio Carrillo de la Plata / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T15:13:15Z (GMT). No. of bitstreams: 1 Santos_MatheusCorreiados_D.pdf: 865476 bytes, checksum: 31a8b558231b701d81c20bf2712e4f50 (MD5) Previous issue date: 2015 / Resumo: Analisaremos dois problemas neste trabalho. Na primeira parte, estudaremos a existência de soluções para uma equação elíptica semilinear no espaço euclidiano todo e com dependência do gradiente e onde nenhuma restrição é imposta sobre o comportamento da não linearidade no infinito. Provaremos que existe uma solução que é localmente única e que herda muitas das propriedades de simetria da não linearidade. A positividade da solução e seu comportamento assintótico também são analisados. Os resultados obtidos também podem ser estendidos para outros casos como o de domínios exteriores ou o semiespaço e também para alguns operadores fracionários. Na segunda parte, analisaremos o comportamento assintótico das soluções da versão fracionária unidimensional da equações de meios porosos introduzida por Caffarelli e Vázquez e onde a pressão é obtida como a inversa do laplaciano fracionário da densidade. Devido à convexidade do núcleo do potencial de Riesz em dimensão um, mostraremos que a entropia associada à equação é displacement convex e satisfaz uma desigualdade funcional envolvendo a dissipação da entropia e a distância de transporte euclidiana. Um argumento por aproximação mostra que essa desigualdade funcional é suficiente para deduzir que a entropia das soluções converge exponencialmente para a entropia do estado estacionário. Também provaremos uma nova desigualdade de interpolação que permitirá obter a convergência exponencial das soluções em espaços Lp / Abstract: We analyse two problems in this work. In the first part we study the existence of solutions to a semilinear elliptic equation in the whole space and with dependence on the gradient and where no restriction is imposed on the behavior of the nonlinearity at infinity. We prove that there exists a solution which is locally unique and inherits many of the symmetry properties of the nonlinearity. Positivity and asymptotic behavior of the solution are also addressed. Our results can be extended to other domains like half-space and exterior domains and also to some fractional operators. For the second part, we analyse the asymptotic behavior of solutions to the one dimensional fractional version of the porous medium equation introduced by Caffarelli and Vázquez and where the pressure is obtained as the inverse of the fractional Laplacian of the density. Due to the convexity of the kernel of the Riesz potential in one dimension, we show that the entropy associated with the equation is displacement convex and satisfies a functional inequality involving also entropy dissipation and the Euclidean transport distance. An argument by approximation shows that this functional inequality is enough to deduce the exponential convergence, in the entropy level, of solutions to the unique steady state. A new interpolation inequality is also proved in order to obtain the exponential decay also in Lp spaces / Doutorado / Matematica / Doutor em Matemática