🔢 mathematics

A reduced-order model for parametrized Optimal Transport problems

This paper proposes a reduced-order modeling approach for parametrized optimal transport problems that constrains the solution to low-dimensional subspaces to formulate a small-scale linear program, accompanied by explicit solvability conditions, a posteriori error estimators enhanced by Empirical Interpolation, and validation on 1D and image color transfer tasks.

Original authors: Elise Bonnet-Weill, Virginie Ehrlacher, Luca Nenna

Published 2026-04-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Elise Bonnet-Weill, Virginie Ehrlacher, Luca Nenna

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master chef running a massive, high-end restaurant. Every day, you have to solve a complex logistical puzzle: How do you move ingredients from your storage (Source) to your kitchen stations (Target) in the most efficient way possible, minimizing waste and travel time?

In the world of mathematics, this is called Optimal Transport. It's used for everything from moving data in AI to matching colors in photos.

The problem is that when your restaurant gets huge (millions of ingredients and stations), solving this puzzle for one day takes hours. But what if you need to solve it for every possible variation of your menu? Maybe you change the amount of flour, the type of sugar, or the season. If you have to run the full, slow calculation for every single variation, you'll never get dinner served.

This paper introduces a clever shortcut: A "Reduced-Order Model." Think of it as creating a "cheat sheet" or a "training manual" so you can solve these puzzles in seconds instead of hours.

Here is how they did it, broken down into simple concepts:

1. The Problem: The "High-Fidelity" Nightmare

The "High-Fidelity" model is the super-accurate, super-slow way of solving the problem. It calculates every single possible route for every single grain of rice.

Analogy: Imagine trying to find the best route for a delivery truck by simulating every single car on the road, every traffic light, and every pedestrian for every possible destination. It's perfect, but it takes forever.

2. The Solution: Learning from "Snapshots"

Instead of calculating everything from scratch every time, the authors say: "Let's look at how we solved this problem 10 or 20 times in the past."

They take a few "snapshots" (examples) of the solution.

The Primal Approach (The Transport Plan): Imagine you have 10 photos of how you moved ingredients for different menus. You realize that most new menus are just a mix of these old ones. So, instead of calculating a new route, you just say, "Okay, this new menu is 30% like Menu A and 70% like Menu B." You mix the old solutions together.
The Dual Approach (The Potentials): In math, there's a second way to look at the problem (like looking at the price tags instead of the routes). They do the same thing: they create a small library of "price tag patterns" and mix those to solve new problems.

3. The Magic Trick: The "Cheat Sheet" (Reduced Basis)

By mixing these old solutions, they create a small, compressed version of the problem.

Analogy: Instead of carrying a 1,000-page encyclopedia of every possible traffic pattern, you carry a 5-page cheat sheet that says, "If it rains, do X; if it's rush hour, do Y."
This "cheat sheet" is the Reduced-Order Model. It has very few variables (degrees of freedom) but captures the essence of the complex problem.

4. Making Sure It's Safe: The "Error Check"

You might worry: "If I use a cheat sheet, will I make a mistake? Will I send the wrong ingredients?"

The authors built two safety nets (called A Posteriori Error Estimators):

The "Double-Check" (c-transforms): They take their quick answer and run a specific mathematical test to see how far off it might be from the perfect answer.
The "Neighbor Check" (Continuity): They know that if you change the menu just a tiny bit, the solution shouldn't change wildly. They use this logic to estimate the error based on how close the current problem is to a problem they already solved perfectly.

If the error is too high, they know to stop and do the full calculation. If it's low, they trust the cheat sheet.

5. The Real-World Test: Painting with Math

To prove it works, they applied this to Color Transfer.

The Task: Take a photo of a gray, boring landscape and make it look like it was painted by a famous artist (like Van Gogh or Delaunay) by matching the colors.
The Result:
- Old Way (Sinkhorn Algorithm): Takes about 7 seconds to transfer colors for one image.
- New Way (Reduced Model): Takes 0.02 seconds.
- Speed Up: 333 times faster!

The images looked almost identical, but the new method was lightning fast. This is huge for things like video editing, where you need to change colors for thousands of frames in real-time.

Summary

This paper is about teaching a computer to learn from its past mistakes so it doesn't have to re-invent the wheel every time.

Before: Solve the whole puzzle from scratch every time (Slow, accurate).
After: Look at a few past puzzles, mix their solutions, and use a "cheat sheet" to solve the new one instantly (Fast, nearly as accurate, with a built-in safety check).

It's the difference between calculating the perfect flight path for a plane every time you fly, versus having a pilot who knows the general wind patterns and can adjust the course in seconds.

1. Problem Statement

The paper addresses the computational bottleneck associated with solving parametrized Optimal Transport (OT) problems. In many applications (e.g., uncertainty quantification, shape optimization, color transfer), one must repeatedly solve large-scale OT problems where the source and target probability measures vary according to a parameter $\alpha$ .

High-Fidelity Model: The standard discrete OT problem is formulated as a Linear Program (LP) with $N_x N_y$ variables (the transport plan) and $N_x + N_y$ constraints. Solving this for a single parameter instance is computationally expensive; solving it for a sweep of parameters is often prohibitive.
Goal: To construct a Reduced-Order Model (ROM) that approximates the solution (specifically the Kantorovich potentials and transport plans) for any parameter $\alpha$ with a computational cost independent of the high-fidelity dimension ( $N_x N_y$ ).

2. Methodology

The authors propose a Reduced Basis (RB) strategy tailored specifically for the structure of OT problems, utilizing both the primal (transport plan) and dual (Kantorovich potentials) formulations.

A. Construction of Reduced Spaces

The method relies on an offline-online decomposition:

Offline Phase:
- A training set of parameters $A_{train}$ is selected.
- Primal Space ( $W^+$ ): A non-negative cone is constructed by stacking the optimal transport plans $\pi^*(\alpha)$ obtained from the high-fidelity solver for the training parameters.
- Dual Spaces ( $U, V$ ): Subspaces are constructed using the Kantorovich potentials $(\phi^*, \psi^*)$ from the training set.
- Basis Selection: The paper proposes using Gram-Schmidt orthogonalization on the marginal distributions to construct the dual bases $U$ and $V$ . This ensures a specific rank condition that guarantees the equivalence between the "semi-reduced" and "fully reduced" models.
Online Phase:
- For a new parameter $\alpha$ , the solution is sought within the reduced spaces.
- The primal solution is approximated as a conic combination of the basis vectors: $\hat{\pi}(\alpha) = \sum p_r(\alpha) w_r$ with $p_r \geq 0$ .
- The dual solution is approximated as a linear combination: $\hat{\phi}(\alpha) = \sum a_n(\alpha) u_n$ and $\hat{\psi}(\alpha) = \sum b_m(\alpha) v_m$ .
- This transforms the original large LP into a small-scale LP with $R$ variables (where $R \ll N_x N_y$ ) and $N+M$ constraints.

B. Theoretical Guarantees

Existence of Solutions: The authors prove that if the training set includes the extreme points of the parameter space (which is a convex polytope), the feasible set of the reduced primal problem is non-empty. Furthermore, if the basis vectors include the constant vector $\mathbf{1}$ (or satisfy specific rank conditions via Gram-Schmidt), the feasible set is compact, ensuring the existence of an optimal solution.
Equivalence: Under specific rank conditions (satisfied by the proposed Gram-Schmidt construction), the optimal value of the fully reduced model is identical to that of the semi-reduced model (where only the primal is reduced).

C. A Posteriori Error Estimation

To certify the accuracy of the ROM without solving the high-fidelity problem, two error estimators are proposed:

C-Transform Based Estimator: Uses the duality gap. It constructs admissible potentials for the high-fidelity dual problem using the reduced potentials and their $c$ $c$ -transforms. The error bound is the difference between the reduced primal cost and this admissible dual cost.
- Challenge: Computing $c$ -transforms is non-linear and expensive ( $O(N_x N_y)$ ).
- Solution: The Empirical Interpolation Method (EIM) is used to approximate the $c$ -transform efficiently, maintaining the offline-online complexity separation.
Continuity-Based Estimator: Leverages the proven Lipschitz continuity of the optimal cost with respect to the parameter $\alpha$ . The error is bounded by the distance to the nearest training parameter plus the known continuity constant.

D. High-Dimensional Reconstruction

A critical contribution is the method to reconstruct a transport map from the reduced solution without explicitly forming the massive matrix $W$ .

The reduced solution is a convex combination of high-fidelity plans.
The transport map is reconstructed by applying the standard "barycentric projection" formula to this convex combination, effectively reducing the reconstruction cost from $O(N_x N_y)$ to $O(R N_x)$ .

3. Key Contributions

Novel ROM Formulation: A primal-dual reduced basis approach specifically designed for parametrized OT, handling the non-negativity constraints of the transport plan and the additive constant ambiguity of potentials.
Rigorous Existence Theory: Explicit conditions (inclusion of extreme points in training, rank conditions on dual bases) ensuring the reduced problem is well-posed and has solutions.
Certified Error Estimation: Development of computable a posteriori error bounds, including an efficient EIM-based approximation for the non-linear terms required by the $c$ -transform estimator.
Efficient Reconstruction: A strategy to recover high-dimensional transport maps from low-dimensional reduced solutions, avoiding the storage of the full transport plan matrix.

4. Numerical Results

The methodology was tested on two scenarios:

1D Parametrized OT:
- Setup: Transport between 1D Gaussian mixtures with varying means and weights ( $N_x=N_y=100$ ).
- Performance: The ROM achieved significant speedups compared to the standard linprog solver and the Sinkhorn algorithm.
- Accuracy: As the number of snapshots (basis size) increased, the error decreased. The ROM achieved comparable or better accuracy than Sinkhorn for a given computational budget, with speedups of several orders of magnitude.
- Error Estimation: The EIM-based error estimator provided tight bounds, though it required correction factors (learned from a small training set) to match the exact error closely.
Color Transfer (3D Application):
- Setup: Transferring color histograms between images (3D histograms, $N \approx 2.6 \times 10^5$ ).
- Performance: Using a reduced basis of only 3 snapshots, the method achieved a 333x speedup compared to the high-fidelity Sinkhorn solver (0.02s vs 6.93s per query).
- Visual Quality: The visual results were nearly indistinguishable from the high-fidelity solution, with only minor differences in color vividness observed upon close inspection.

5. Significance

This work bridges the gap between Model Order Reduction (MOR) and Optimal Transport. While previous MOR applications in OT focused on using OT to solve PDEs (e.g., advection-dominated flows), this paper treats the OT problem itself as the parametric object of interest.

Real-Time Applicability: The ability to solve complex, high-dimensional OT problems in milliseconds makes real-time applications (like interactive color grading or rapid uncertainty quantification) feasible.
Theoretical Rigor: It provides the first rigorous framework for reduced basis approximation of Kantorovich potentials with certified error bounds, addressing challenges like multi-valued solutions (additive constants) and non-negativity constraints.
Scalability: By avoiding the explicit construction of the full transport plan matrix during the online phase, the method scales to high-dimensional problems (like 3D color histograms) that are typically intractable for standard LP solvers.