Lectures on Optimal Transport pp 1322Cite as, Part of the UNITEXT book series (UNITEXTMAT,volume 130). Without loss of generality we can assume that \(\int _{\Omega} \vert u \vert ^{p-2} u\,\mathrm{d}x=0\). Adv. Note that Kantorovich potentials are typically not unique, which is why it is interesting to verify that the limiting procedure \(p\to \infty \) selects a more regular potential. 2016-06596. 3, 146158 (1975), Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. Now we also give a PDE characterization of the limit \(u_{\infty}\), which we have shown to be a Kantorovich potential in the previous section. Learn more about Stack Overflow the company, and our products. Eur. Let \(\mu \in \mathcal {M}(\overline{\Omega })\) and , where \(\lim_{p\to \infty}\varepsilon _{p}=0\) and \(\mu ^{\varepsilon _{p}}\) is defined as in (3.20). [4], The Nobel Memorial Prize, which he shared with Tjalling Koopmans, was given "for their contributions to the theory of optimum allocation of resources.". The following are our main results. In more detail, Sect. An upper semicontinuous function \(u:\overline{\Omega }\to \mathbb{R}\) is called viscosity subsolution of (1.1) if, for all \(x_{0}\in \Omega \) and \(\phi \in C^{2}(\Omega )\) such that \(u-\phi \) has a local maximum at \(x_{0}\), it holds, for all \(x_{0}\in \partial \Omega \) and \(\phi \in C^{2}(\overline{\Omega })\) such that \(u-\phi \) has a local maximum at \(x_{0}\), it holds. Im waiting for my US passport (am a dual citizen). Springer, Berlin (2011), Book It involves the concept of transport plan (also called coupling in the Probability literature) between probability measures. Provided by the Springer Nature SharedIt content-sharing initiative. Math. 1. : Entropy minimization, \(DAD\) problems, and doubly stochastic kernels. Google Scholar, Fllmer, H., Gantert, N.: Entropy minimization and Schrdinger processes in infinite dimensions. 49(2), 13851418 (2017), Cominetti, R., San Martn, J.: Asymptotic analysis of the exponential penalty trajectory in linear programming. Let us first define what it means to be a viscosity solution to the p-Poisson equation(1.1). This makes sure that one can pass to the limit in duality products where both factors converge, as the following lemma shows. [1] His father was a doctor practicing in Saint Petersburg. To this end, we first derive an upper bound for the p-Dirichlet energy \(\int _{\Omega} \vert \nabla u \vert ^{p}\,\mathrm{d}x\) in terms of the data, which will then allow us to deduce convergence. volume2023, Articlenumber:8 (2023) 3.1 proves compactness of solutions of (1.1) as \(p\to \infty \), Sect. requires optimizing two time-invariant Entropy-Kantorovich potential functions 'and . Entropic Optimal Transport: Convergence of Potentials A. Fathi and A. Figalli, Optimal transportation on non-compact manifolds. \end{aligned}$$, $$\begin{aligned} \limsup_{p\to \infty} \vert \mu _{p} \vert ( \overline{ \Omega })< \infty. 36, 423439 (1965), Stroock, D.W., Varadhan, S.R.S. For example your corollary 2 fails if my measure $\mu$ is only supported on the boundary $\partial\Omega$, does it not? 2). [2210.07830] Asymptotic of the Kantorovich potential for the optimal Introduction The optimal transport problem is intimately tied to the theory of second- $$W_1(p,q) = \sup_{|f|_L\leq 1} \int f(x)(p(x)-q(x))dx$$, $$f_*^{p,q}=\arg\sup_{|f|_L\leq 1} \int f(x)(p(x)-q(x))dx$$, $$\nabla_{p\to p'} f_*^{p,q}(x)=\frac{d}{d\tau} f_*^{p+\tau p',q}(x)|_{\tau=0}$$. $$\sup\{\int_Y \varphi(y) d\nu(y) - \int_X \psi(x) d\mu(x):\ Commun. } : Multidimensional Diffusion Processes. PDF Abstract 1 Introduction - ResearchGate Theory Relat. The function $p+\tau p'$ is not a probability measure. \end{aligned}$$, $$\begin{aligned} \liminf_{p\to \infty} \biggl( \int _{\Omega} \vert u_{p} \vert ^{p-k}\, \mathrm{d}x \biggr)^{\frac{1}{p-k}} \geq -\varepsilon + \operatorname{ess\,sup}_{\Omega} \vert u_{\infty } \vert . Math. View all Google Scholar citations A solution of the Kantorovich dual problem is called Kantorovich potential. Corrected reprint of the second (1998) edition, Di Marino, S., Gerolin, A.: An optimal transport approach for the Schrdinger bridge problem and convergence of Sinkhorn algorithm. Anyone you share the following link with will be able to read this content: Sorry, a shareable link is not currently available for this article. He calculated the optimal distance between cars on ice in dependence of the thickness of ice and the temperature of the air. \end{aligned}$$, \(\vert \nabla \phi (x_{0}) \vert -1\leq 0\), \(\vert \nabla \phi (x_{0}) \vert -1 > 0\), \(x_{0}\in {\overline{\{\mu \neq 0\}}^{c}}\), $$\begin{aligned} -\Delta _{\infty }\phi (x_{0})\leq 0. Site design / logo 2023 Stack Exchange Inc; user contributions licensed under CC BY-SA. PubMedGoogle Scholar. J. Funct. Dyn. What's the correct way to think about wood's integrity when driving screws? 2023 Springer Nature Switzerland AG. If \(1- \vert \nabla \phi (x_{0}) \vert \leq 0\), then in the limit \(i\to \infty \) and using the uniform boundedness of \(\mu _{p_{i}}\) we get \(-\Delta _{\infty }\phi (x_{0}) \leq 0\) If, however, \(1- \vert \nabla \phi (x_{0}) \vert >0\), one gets \(-\Delta _{\infty}\phi (x_{0})\leq -\infty \) as \(i\to \infty \), which is impossible since \(\phi \in \mathrm{C}^{2}(\Omega )\). As it turns out, the correct metric on when working with (1.1) (or (2.4)) and its limit as \(p\to \infty \) is not the Euclidean one but the geodesic distance. The proof works just as in [9, Proposition4.3], see also [18, Lemma2.1]. : The Neumann problem for the -Laplacian and the MongeKantorovich mass transfer problem. Calculus of variations, PDEs, and modeling, Progress in Nonlinear Differential Equations and Their Applications 87. A derived quantity, which appears naturally in the context of the Neumann problem (1.1), is the geodesic diameter of , defined as, The geodesic diameter appears in the optimal constant in the inequality, and in the first nontrivial Neumann eigenvalue of the infinity Laplacian [8, 15], given by, One can use the geodesic distance to define the geodesic Lipschitz constant of \(u\in \mathrm{C}(\overline{\Omega })\) as. Comput. rev2023.6.5.43477. Kantorovich considered infinite-dimensional optimization problems, such as the Kantorovich-Monge problem in transport theory. [2] In 1926, at the age of fourteen, he began his studies at Leningrad State University. (Viscosity solutions of the limiting equation), Let \(\mu \in \mathrm{C}(\overline{\Omega })\). For measuring the convergence of the right-hand side measures \(\mu _{p}\) in (1.1) as \(p\to \infty \), we utilize weak-star convergence of measures. Now that the company takes up the transportation charge, their problem is to maximize the profits. 17(5), 369375 (1993), Rschendorf, L., Thomsen, W.: Closedness of sum spaces and the generalized Schrdinger problem. So why trouble yourself with uniqueness of the potentials themselves. Are there known optimal (?) In: Borges, O., Button, L., Welling, M., Ghahramani, Z., Weinberger, U.Q. your institution, https://www.math.columbia.edu/~mnutz/docs/EOT_lecture_notes.pdf. : Self-consistent equations including exchange and correlation effects. Math. Computation of integration wrt counting measure. does not charge n 1-dimensional rectifiable sets. Soc. Replication crisis in theoretical computer science? University of Jyvaskyla, Jyvaskyla (2017), Lindgren, E., Lindqvist, P.: Regularity of the p-Poisson equation in the plane. Abstract We prove a conjecture regarding the asymptotic behavior at infinity of the Kantorovich potential for the Multimarginal Optimal Transport with Coulomb and Riesz costs. Appl. $\newcommand{\R}{\mathbb R}$Take $\Omega\subset \R^d$ bounded, convex, and smooth. The method completely avoids solving an ODE during training. Anal. Since \(u_{\infty}\) turns out to solve an infinity Laplacian type PDE in the viscosity sense, we also have to work with viscosity solutions for finitep. However, for that we have to assume that the data \(\mu _{p}\) are continuous and converge uniformly. Math. We study the potential functions that determine the optimal density for \(\varepsilon \)-entropically regularized optimal transport, the so-called Schrdinger potentials, and their convergence to the counterparts in classical optimal transport, the Kantorovich potentials. \end{aligned}$$, \(\operatorname{ess\,sup}_{\Omega} \vert u \vert \leq 1\), \(\Vert \mu \Vert _{\mathrm{KR}(\overline{\Omega })}\leq \Vert \mu \Vert _{\operatorname{Lip}_{\Omega}^{\ast}( \overline{\Omega })}\), \(\operatorname{ess\,sup}_{\Omega }u +\operatorname{ess\,inf}_{\Omega }u = 0\), $$\begin{aligned} \operatorname{ess\,sup}_{\Omega} \vert u \vert \leq \frac{\operatorname{diam}(\Omega )}{2} \underbrace{ \operatorname{ess\,sup}_{\Omega} \vert \nabla u \vert }_{= \operatorname{Lip}_{\Omega}(u)} \leq \frac{\operatorname{diam}(\Omega )}{2}. In the limit \(\varepsilon \rightarrow 0\) of vanishing regularization, strong compactness holds in \(L^{1}\) and cluster points are Kantorovich potentials. The best answers are voted up and rise to the top, Not the answer you're looking for? For his feat and courage Kantorovich was awarded the Order of the Patriotic War, and was decorated with the medal For Defense of Leningrad. Can one deduce the geometry of the plan from the potential and vice versa? Reprint of the 1997 edition, Institute for Advanced Study, School of Mathematics, Princeton, NY, USA, Mathematical Institute, University of Oxford, Oxford, UK, You can also search for this author in Similar results have already been established for several related problems associated with the p-Laplace operator. In particular, Kantorovich formulated some fundamental results in the theory of normed vector lattices, especially in Dedekind complete vector lattices called "K-spaces" which are now referred to as "Kantorovich spaces" in his honor. Google Scholar, Ziemer, W.P. The author declares that he has no competing interests. This is illustrated in the following example. As always, there exists a sequence of points \((x_{i})_{i\in \mathbb{N}}\subset \Omega \) converging to \(x_{0}\in \Omega \) such that \(u_{p_{i}}-\phi \) has a local maximum in \(x_{i}\) for all \(i\in \mathbb{N}\). In this paper we consider the optimal mass transport problem for relativistic cost functions, introduced in [12] as a generalization of the relativistic heat cost. To subscribe to this RSS feed, copy and paste this URL into your RSS reader. Are you just curious, or looking for research project, or do you have an actual application in mind? Var. it holds \(\int _{\Omega} \vert u \vert ^{p-2}u\,\mathrm{d}x\leq 0\). Case3, \(x_{0}\in {\{\mu <0\}}\): We have to show that. Hausdorff Center for Mathematics, University of Bonn, Endenicher Allee 62, Villa Maria, 53115, Bonn, Germany, You can also search for this author in In either case, we obtain (3.17). Math. Am. is a viscosity solution of, Let \(x_{0}\in {\{\mu >0\}}\) and \(\phi \in \mathrm{C}^{2}(\Omega )\) such that \(u_{\infty}-\phi \) has a local minimum at \(x_{0}\). Browse other questions tagged, Start here for a quick overview of the site, Detailed answers to any questions you might have, Discuss the workings and policies of this site. , To set the scene for the optimal transport characterization, we remind the reader of the usual Wasserstein-1 distance \(W_{1}(\mu ^{+},\mu ^{-})\) of the two measures \(\mu ^{\pm}\), defined as, where the Lipschitz constant \(\operatorname{Lip}( u)\) in (3.8) is. How to check if a string ended with an Escape Sequence (\n). Privacy Using lower and upper semicontinuous envelopes of this discontinuous function, one can make sense of a weaker form of the PDE on the whole of , see [22, Remark4.3] for a similar problem and [20, Remark6.3] for a general statement. Monge's original optimal mass transport problem corresponds to the Euclidean distance. For the balanced case of two labelled classes with equal size, i.e., \(g:\mathcal{O}\to \{\pm 1\}\) and \(\overline{g}=0\), our main results can be interpreted as follows: The labelling function u arising as limit of solutions to Poisson learning as \(p\to \infty \) is directly connected to the solution of the optimal transport problem, which transports the empirical measure \(\sum_{i: g(x_{i})=+1}\delta _{x_{i}}\) of the points with label +1 to the empirical measure \(\sum_{i: g(x_{i})=-1}\delta _{x_{i}}\) of the points with label 1. and supersolutions satisfy the converse inequality with a max in place of the min. 30, 12291263 (2019), CrossRef PDF Kantorovich potentials and continuity of total cost for - CNRS We prove that every limit \(u_{\infty}\) of solutions to the p-Poisson equation (1.1) as \(p\to \infty \) is a viscosity solution of (1.3), which we restate here for convenience: Note that this PDE does not contain any boundary conditions and it also does not specify the behavior on the closed set \(\overline{\Omega }\setminus ({\{\mu >0\}}\cup{\{\mu <0\}}\cup{ \overline{\{\mu \neq 0\}}^{c}} )\). 1) Based on Theorem 5.10(iii) in Villani (2008) you can always assume that the optimal potentials are c-concave. Math. Furthermore, in [6] the case of mixed boundary conditions and regular fixed right-hand sides was related to optimal transport through a window on the boundary. For non-negative The first one is purely variational and states that, if the right-hand sides \(\mu _{p}\) converge weak-star to a measure \(\mu \in \mathcal {M}(\overline{\Omega })\) as \(p\to \infty \), then weak solutions \(u_{p}\) of (1.1) converge (up to a subsequence) to a Kantorovich potential \(u_{\infty}\), which realizes the maximum in the following version of the Wasserstein-1 distance between the positive part \(\mu ^{+}\) and the negative part \(\mu ^{-}\) of : The second result uses techniques from viscosity solutions to prove that for continuous data \(\mu _{p}\in \mathrm{C}(\overline{\Omega })\), converging uniformly to \(\mu \in \mathrm{C}(\overline{\Omega })\), solutions \(u_{p}\) converge to a viscosity solution of the following infinity Laplacian / eikonal type partial differential equation (PDE): Consequently, the only information on , which survives the limit \(p\to \infty \) in the p-Poisson problem (1.1), is the support of its positive and negative part. This could be helpful to extend the scope of your work. |I7pmtp^k.fiZa7C1Qm#T~?gz6=~8F3OIm=S?A==q #%* LQxc#z1n9x`lPdkxK8e}f T!"wf*wZg2Rmj5 \end{cases}\displaystyle \end{aligned}$$, \(\overline{\Omega }\setminus ({\{\mu >0\}}\cup{\{\mu <0\}}\cup{ \overline{\{\mu \neq 0\}}^{c}} )\), $$\begin{aligned} \textstyle\begin{cases} \min \lbrace \vert \nabla \phi (x_{0}) \vert -1,- \Delta _{\infty }\phi (x_{0}) \rbrace \leq 0& \text{if }x_{0} \in {\{\mu >0\}}, \\ -\Delta _{\infty }\phi (x_{0}) \leq 0& \text{if }x_{0}\in { \overline{\{\mu \neq 0\}}^{c}}, \\ \max \lbrace 1- \vert \nabla \phi (x_{0}) \vert ,- \Delta _{\infty }\phi (x_{0}) \rbrace \leq 0& \text{if }x_{0} \in {\{\mu < 0\}}, \end{cases}\displaystyle \end{aligned}$$, \(\max_{\overline{\Omega }} u + \operatorname{ess\,inf}_{\Omega }u \leq 0\), $$\begin{aligned} \textstyle\begin{cases} \min \lbrace \vert \nabla \phi (x_{0}) \vert -1,- \Delta _{\infty }\phi (x_{0}) \rbrace \geq 0& \text{if }x_{0} \in {\{\mu >0\}}, \\ -\Delta _{\infty }\phi (x_{0}) \geq 0& \text{if }x_{0}\in { \overline{\{\mu \neq 0\}}^{c}}, \\ \max \lbrace 1- \vert \nabla \phi (x_{0}) \vert ,- \Delta _{\infty }\phi (x_{0}) \rbrace \geq 0& \text{if }x_{0} \in {\{\mu < 0\}}, \end{cases}\displaystyle \end{aligned}$$, \(\operatorname{ess\,sup}_{\Omega }u + \min_{\overline{\Omega }}u \geq 0\), \(u_{\infty}\in \mathrm{C}(\overline{\Omega })\), \((p_{i})_{i\in \mathbb{N}}\subset (d,\infty )\), \((x_{i})_{i\in \mathbb{N}}\subset \Omega \), $$\begin{aligned} - \bigl( \bigl\vert \nabla \phi (x_{i}) \bigr\vert ^{p_{i}-2} \Delta \phi (x_{i}) + (p_{i}-2) \bigl\vert \nabla \phi (x_{i}) \bigr\vert ^{p_{i}-4}\Delta _{\infty}\phi (x_{i}) \bigr) = - \Delta _{p_{i}}\phi (x_{i}) \leq \mu _{p_{i}}(x_{i}). 32, pp. Rend. Furthermore, there is no \(\phi \in \mathrm{C}^{2}(\Omega )\) touching u from below in \(x_{0}\). We index the right-hand side by p to include the case that it varies withp. In the rest of the paper we will refer to (1.1) as the p-Poisson equation since for \(p=2\) it obviously coincides with the standard Poisson equation. https://www.math.columbia.edu/~mnutz/docs/EOT_lecture_notes.pdf, Pal, S.: On the difference between entropic cost and the optimal transport cost. \end{cases}\displaystyle \end{aligned}$$, $$\begin{aligned} \bigl\vert \nabla \phi (x_{0}) \bigr\vert -1\geq 0\quad \text{and}\quad - \Delta _{\infty}\phi (x_{0})\geq 0. The existence and uniqueness of thesolution can be demonstrated by applying the canonical duality theory. Google Scholar, Berman, R.J.: The Sinkhorn algorithm, parabolic optimal transport and geometric MongeAmpre equations. In: International Conference on Machine Learning, PMLR, pp. LA - eng KW - Monge-Kantorovich problem; optimal transportation; mixed methods; finite elements; . Stack Exchange network consists of 181 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. in advance. MathOverflow is a question and answer site for professional mathematicians. 1. The linear function \(u(x)=x\) is a limit of p-Laplacian solutions, see Example3.1, Since the concept of viscosity solutions heavily relies on continuity and is not compatible with discontinuous or even measure data , we have to use approximation techniques if we want to make sense of (3.13) if is a measure. Part of To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. The results of the present article apply to the continuum description of Poisson learning and, in particular, address the asymptotics as \(p\to \infty \). (Color online) Kantorovich potential v(r) for the beryllium atom \end{aligned}$$, $$\begin{aligned} \operatorname{ess\,sup}_{\Omega} \vert \nabla u_{\infty } \vert = \lim _{m \to \infty} \biggl( \int _{\Omega} \vert \nabla u_{\infty } \vert ^{m}\,\mathrm{d}x \biggr)^{\frac{1}{m}} \leq 1. Kantorovich potential for the optimal transport map between (,) and ( , ) with cost function c. A noteworthy aspect of our work is that c does not necessarily satisfy the weak Ma-Trudinger-Wang condition. But pointwise uniqueness of $\phi, \psi$ is more difficult, and I don't know any references. Mech. If material is not included in the articles Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. J. Combining all those cases yields (3.15). Am. Kantorovich was born on 19 January 1912, to a Russian Jewish family. Google Scholar, Ambrosio, L., Gigli, N., Savar, G.: Gradient Flows in Metric Spaces and in the Space of Probability Measures. , Since according to Proposition3.2 the limit \(u_{\infty}\) also satisfies \(\operatorname{ess\,sup}_{\Omega} \vert u_{\infty } \vert \leq \frac{\operatorname{diam}(\Omega )}{2}\), one could also have the idea to include a boundedness condition in the optimization problem in (2.10). The author read and approved the final manuscript. Building a safer community: Announcing our new Code of Conduct, We are graduating the updated button styling for vote arrows, Statement from SO: June 5, 2023 Moderator Action. He was given the task of optimizing production in a plywood industry. 66(2), 349366 (2007), Article . Let's summarize this stuff under "sufficiently strong regularity conditions" and focus on the main question, examining the potential under perturbations to $p$. Now we can prove the main theorem of this section. Uniqueness of Kantorovich potentials? - MathOverflow ,drN) , (SCE) The Kantorovich Dual of the 1-Wasserstein distance $W_1(p,q)$ between two densities $p(x), q(x)$ is given by It is obvious from the definition of \(\mu _{\varepsilon }\) that if \(x\in \Omega \setminus \operatorname{supp}\mu \) then \(x\in \Omega \setminus \operatorname{supp}\mu ^{\varepsilon }\) for all \(\varepsilon >0\) small enough. 262(4), 18791920 (2012), Lonard, C.: A survey of the Schrdinger problem and some of its connections with optimal transport.
J'adore Dior Fragrantica, Automotive Multimeter Test Leads, Articles K