skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Efficient Approximation of Optimal TransportationMap by Pogorelov Map
Optimal transportation (OT) finds the most economical way to transport one measure to another and plays an important role in geometric modeling and processing. Based on the Brenier theorem, the OT problem is equivalent to the Alexandrov problem, which is the dual to the Pogorelov problem. Although solving the Alexandrov/Pogorelov problem are both equivalent to solving the Monge-Amp\`{e}re equation, the former requires second type boundary condition and the latter requires much simpler Dirichlet boundary condition. Hence, we propose to use the Pogorelov map to approximate the OT map. The Pogorelov problem can be solved by a convex geometric optimization framework, in which we need to ensure the searching inside the admissible space. In this work, we prove the discrete Alexandrov maximum principle, which gives an apriori estimate of the searching. Our experimental results demonstrate that the Pogorelov map does approximate the OT map well with much more efficient computation.  more » « less
Award ID(s):
1762287
PAR ID:
10291683
Author(s) / Creator(s):
; ; ; ; ; ;
Date Published:
Journal Name:
Proceedings of International Meshing Roundtable
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, Proceedings of International Meshing Roundtable)
    null (Ed.)
    Optimal transportation finds the most economical way to transport one probability measure to another, and it plays an important role in geometric modeling and processing. In this paper, we propose a moving mesh method to generate adaptive meshes by optimal transport. Given an initial mesh and a scalar density function defined on the mesh domain, our method will redistribute the mesh nodes such that they are adapted to the density function. Based on the Brenier theorem, solving an optimal transportation problem is reduced to solving a Monge-Amp\`ere equation, which is difficult to compute due to the high non-linearity. On the other hand, the optimal transportation problem is equivalent to the Alexandrov problem, which can finally induce an effective variational algorithm. Experiments show that our proposed method finds the adaptive mesh quickly and efficiently. 
    more » « less
  2. ; (, Proceedings of International Conference on Computer Vision (ICCV))
    null (Ed.)
    An optimal transportation map finds the most economical way to transport one probability measure to the other. It has been applied in a broad range of applications in vision, deep learning and medical images. By Brenier theory, computing the optimal transport map is equivalent to solving a Monge-Amp\`ere equation. Due to the highly non-linear nature, the computation of optimal transportation maps in large scale is very challenging. This work proposes a simple but powerful method, the FFT-OT algorithm, to tackle this difficulty based on three key ideas. First, solving Monge-Amp\`ere equation is converted to a fixed point problem; Second, the obliqueness property of optimal transportation maps are reformulated as Neumann boundary conditions on rectangular domains; Third, FFT is applied in each iteration to solve a Poisson equation in order to improve the efficiency. Experiments on surfaces captured from 3D scanning and reconstructed from medical imaging are conducted, and compared with other existing methods. Our experimental results show that the proposed FFT-OT algorithm is simple, general and scalable with high efficiency and accuracy. 
    more » « less
  3. ; (, Information and Inference: A Journal of the IMA)
    Abstract In the standard formulation of the classical denoising problem, one is given a probabilistic model relating a latent variable $$\varTheta \in \varOmega \subset{\mathbb{R}}^{m} \; (m\ge 1)$$ and an observation $$Z \in{\mathbb{R}}^{d}$$ according to $$Z \mid \varTheta \sim p(\cdot \mid \varTheta )$$ and $$\varTheta \sim G^{*}$$, and the goal is to construct a map to recover the latent variable from the observation. The posterior mean, a natural candidate for estimating $$\varTheta $$ from $$Z$$, attains the minimum Bayes risk (under the squared error loss) but at the expense of over-shrinking the $$Z$$, and in general may fail to capture the geometric features of the prior distribution $$G^{*}$$ (e.g. low dimensionality, discreteness, sparsity). To rectify these drawbacks, in this paper we take a new perspective on this denoising problem that is inspired by optimal transport (OT) theory and use it to study a different, OT-based, denoiser at the population level setting. We rigorously prove that, under general assumptions on the model, this OT-based denoiser is mathematically well-defined and unique, and is closely connected to the solution to a Monge OT problem. We then prove that, under appropriate identifiability assumptions on the model, the OT-based denoiser can be recovered solely from information of the marginal distribution of $$Z$$ and the posterior mean of the model, after solving a linear relaxation problem over a suitable space of couplings that is reminiscent of standard multimarginal OT problems. In particular, due to Tweedie’s formula, when the likelihood model $$\{ p(\cdot \mid \theta ) \}_{\theta \in \varOmega }$$ is an exponential family of distributions, the OT-based denoiser can be recovered solely from the marginal distribution of $$Z$$. In general, our family of OT-like relaxations is of interest in its own right and for the denoising problem suggests alternative numerical methods inspired by the rich literature on computational OT. 
    more » « less
  4. ; (, Lecture notes in computer science)
    Sistek, J.; Tichy, P; Kozubek, T.; Cermak, M.; Lukas, D.; Jaros, J.; Blaheta, R. (Ed.)
    We introduce an efficient method for computing the Stekloff eigenvalues associated with the indefinite Helmholtz equation. In general, this eigenvalue problem requires solving the Helmholtz equation with Dirichlet and/or Neumann boundary condition repeatedly. We propose solving the discretized problem with Fast Fourier Transform (FFT) based on carefully designed extensions and restrictions operators. The proposed Fourier method, combined with proper eigensolver, results in an efficient and easy approach for computing the Stekloff eigenvalues 
    more » « less
  5. ; (, Journal für die reine und angewandte Mathematik (Crelles Journal))
    Abstract Let S be a surface with a metric d satisfying an upper curvature bound in the sense of Alexandrov (i.e. via triangle comparison).We show that an almost conformal harmonic map from a surface into ( S , d ) {(S,d)} is a branched covering. As a consequence, if ( S , d ) {(S,d)} is homeomorphically equivalent to the 2-sphere 𝕊 2 {\mathbb{S}^{2}} , then it is conformally equivalent to 𝕊 2 {\mathbb{S}^{2}} . 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email