Optimal Transport Approximation of 2-Dimensional Measures

DOI10.1137/18M1193736zbMATH Open1524.65097arXiv1804.08356OpenAlexW2913142797WikidataQ127989346 ScholiaQ127989346MaRDI QIDQ6175992FDOQ6175992

Authors: Léo Lebrat, Frédéric De Gournay, Jonas Kahn, Pierre Weiss 

Publication date: 25 July 2023

Published in: SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Abstract: We propose a fast and scalable algorithm to project a given density on a set of structured measures defined over a compact 2D domain. The measures can be discrete or supported on curves for instance. The proposed principle and algorithm are a natural generalization of previous results revolving around the generation of blue-noise point distributions, such as Lloyd's algorithm or more advanced techniques based on power diagrams. We analyze the convergence properties and propose new approaches to accelerate the generation of point distributions. We also design new algorithms to project curves onto spaces of curves with bounded length and curvature or speed and acceleration. We illustrate the algorithm's interest through applications in advanced sampling theory, non-photorealistic rendering and path planning.

Full work available at URL: https://arxiv.org/abs/1804.08356

zbMATH Keywords

optimizationWasserstein distancequantizationsampling theorymeasure theorypath planningcurve projectionblue noisenonphotorealistic rendering

Mathematics Subject Classification ID

Optimal transportation (49Q22) Numerical smoothing, curve fitting (65D10) Newton-type methods (49M15) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Cites Work

• Numerical Optimization
• Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM
• Least squares quantization in PCM
• The geometry of optimal transportation
• Gradient methods for minimizing composite functions
• A fast algorithm for particle simulations
• Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
• Proximal splitting methods in signal processing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Minkowski-type theorems and least-squares clustering
• Motion of level sets by mean curvature. I
• Power Diagrams: Properties, Algorithms and Applications
• On alternating direction methods of multipliers: a historical perspective
• Affine plane curve evolution: a fully consistent scheme
• Centroidal Voronoi Tessellations: Applications and Algorithms
• Consistency of variational continuous-domain quantization via kinetic theory
• Simple examples for the failure of Newton's method with line search for strictly convex minimization
• Dithering by differences of convex functions
• Fast Summation at Nonequispaced Knots by NFFT
• Optimal Delaunay and Voronoi quantization schemes for pricing American style options
• Regularized Newton method for unconstrained convex optimization
• Breaking the coherence barrier: a new theory for compressed sensing
• A projection method on measures sets
• On the generation of sampling schemes for magnetic resonance imaging
• Convergence of a Newton algorithm for semi-discrete optimal transport
• A numerical algorithm for \(L_2\) semi-discrete optimal transport in 3D
• Global convergence of splitting methods for nonconvex composite optimization
• Comparison between \(W_2\) distance and \(\dot{H}^{-1}\) norm, and localization of Wasserstein distance
• Regularized Newton methods for minimizing functions with Hölder continuous hessians
• Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure
• An algorithm for variable density sampling with block-constrained acquisition
• An algorithm for optimal transport between a simplex soup and a point cloud
• Title not available (Why is that?)

Cited In (8)

• 3/4-discrete optimal transport
• Curve based approximation of measures on manifolds by discrepancy minimization
• Second-order models for optimal transport and cubic splines on the Wasserstein Space
• From optimal transport to discrepancy
• Spectral decomposition of discrepancy kernels on the Euclidean ball, the special orthogonal group, and the Grassmannian manifold
• A new optimal transport distance on the space of finite Radon measures
• One-dimensional approximation of measures in Wasserstein distance
• On Optimal Transport of Matrix-Valued Measures

This page was built for publication: Optimal Transport Approximation of 2-Dimensional Measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6175992)