TL;DR
This paper presents a novel numerical method for solving the Optimal Transportation (OT) problem by discretizing the Monge-Ampère equation with a new approach to handling boundary conditions. This method is efficient, robust, and capable of handling complex, non-convex domains, offering a significant improvement over existing techniques.
What Problem Does This Paper Address?
The Optimal Transportation (OT) problem, a fundamental concept in mathematics and various applied fields, seeks to find the most efficient way to move mass from one distribution to another. While the theory behind OT is well-developed, its numerical solution, particularly for complex scenarios, has remained a significant challenge. This paper tackles the difficulty of numerically solving the Monge-Ampère Partial Differential Equation (PDE), which arises from the OT problem, especially when dealing with non-standard boundary conditions and potentially singular solutions. Existing methods often struggle with accuracy, speed, or the ability to handle non-convex or disconnected domains.
Methods
The authors propose a numerical method that combines a finite difference scheme for the Monge-Ampère equation with a novel approach to discretizing the boundary conditions. Key aspects of their method include:
- Monge-Ampère Equation Discretization: They employ a "convergent filtered discretization" that blends a monotone, low-accuracy scheme with a more accurate one. This approach, inspired by previous work, aims to achieve good accuracy while maintaining stability.
- Boundary Condition Handling: A crucial contribution is the treatment of the OT boundary conditions, which are typically difficult to implement. They replace the standard boundary condition with a Hamilton-Jacobi equation on the boundary, using a signed distance function to the target set. This allows for a monotone finite difference scheme for the boundary, consistent with the interior PDE.
- Newton's Method: To efficiently solve the resulting system of nonlinear equations, they utilize Newton's method. This involves computing Jacobians for both the interior and boundary discretizations.
- Compact Stencil: For practical implementation, they focus on a "compact, narrow-stencil" version of the scheme, which simplifies the method and improves computational efficiency without sacrificing accuracy in most cases.
Datasets
Not discussed in the paper. The paper focuses on developing and testing a numerical method using synthetic examples with known or analytically derived solutions.
Key Insights and Ideas
- Boundary Condition Reformulation: The key insight is reformulating the complex OT boundary conditions into a Hamilton-Jacobi equation that can be discretized using finite differences, making it amenable to numerical solvers.
- Robustness to Singularities: The method demonstrates robustness in handling solutions with singularities, which are common in OT problems, and can even deal with non-convex and disconnected domains.
- Efficiency of Newton's Method: The application of Newton's method to solve the discretized system, including the implicit boundary conditions, leads to a remarkably fast solver, comparable to solving the much simpler Laplace equation multiple times.
- Compact Stencil Advantage: The finding that a compact stencil can achieve good accuracy for most cases, despite theoretical requirements for wider stencils in some singular scenarios, significantly simplifies the implementation and improves performance.
Key Results
The paper presents several computational examples demonstrating the method's effectiveness:
- Accuracy: For smooth problems like mapping a square to a square or an ellipse to an ellipse, the method achieves first-order accuracy, with errors decreasing as the grid resolution increases.
- Speed: The solver is very fast, with computation times comparable to solving the Laplace equation. For instance, mapping a square to a square with a grid of 256x256 points takes around 41.6 seconds.
- Robustness: The method successfully handles challenging cases, including:
- Mapping from a disconnected region (two half-circles to a circle).
- Inverse mapping with non-constant densities.
- Mapping from a non-convex source domain.
- "Pogorelov solutions" involving singular target densities (sums of Dirac masses).
- Scalability: The computational time is observed to be linear with respect to the number of grid points, and importantly, independent of the number of Dirac masses in the target density for the Pogorelov solutions.
Limitations and Future Work
- Limitations:
- While the method is robust, the convergence proof in the companion paper [BFO12] is for specific conditions (positive, Lipschitz continuous, non-vanishing target density on a convex set). Some of the tested examples (e.g., singular solutions, non-convex domains) fall outside these strict theoretical guarantees, though they perform well in practice.
- For extremely singular solutions, a wider stencil might be necessary for higher accuracy, though the compact stencil is sufficient for many cases.
- The paper mentions that the numerical solution of Pogorelov problems yields a convex piecewise affine potential, which is not strictly a viscosity solution, thus outside the convergence theory.
- Future Work:
- Generalizing the method to three dimensions.
- Improving the linear solver within Newton's method (currently using a direct solver, suggesting an iterative solver could boost performance).
- Extending the method to compute JKO gradient flows by using linearized equations to estimate the gradient.
Summary updated