Computer Graphics Forum · 2011 · 272 citations · 20 references
ComputingComputer ScienceMathematicsMultiscale ModelingOptimizationTransportApproximation AlgorithmsTransport ModelingTransport ModellingTransportation ProblemsConstraintsMultiscale OptimizationMultiscale RepresentationOptimal TransportProbability Density AnalysisProbability Density Maps
The paper proposes an improved algorithm for least‑square matching between a probability density and a finite set of mass‑constrained sites in the Euclidean plane. The algorithm uses a multiscale approach, iteratively simplifying the target with Lloyd's algorithm and using the simplified solution as an initial guess for the full problem, and the authors compare this multiscale version to the original implementation. The multiscale method enables rapid estimation of Earth‑mover/Wasserstein distances between measures.
Abstract In this paper, we propose an improvement of an algorithm of Aurenhammer, Hoffmann and Aronov to find a least square matching between a probability density and finite set of sites with mass constraints, in the Euclidean plane. Our algorithm exploits the multiscale nature of this optimal transport problem. We iteratively simplify the target using Lloyd's algorithm, and use the solution of the simplified problem as a rough initial solution to the more complex one. This approach allows for fast estimation of distances between measures related to optimal transport (known as Earth‐mover or Wasserstein distances). We also discuss the implementation of these algorithms, and compare the original one to its multiscale counterpart.
20
Practical methods of optimization
Mathematics and Computers in Simulation · 1988 · 5.9K citations
A Convexity Principle for Interacting Gases
Robert J. McCann · Advances in Mathematics · 1997 · 923 citations