Sparse Optimal Transport via Quadratic and f-Divergence Regularization

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 286 papers148 conceptsfrozen 2026-10-04

Optimal Transport (OT) is the mathematical framework for finding the most efficient way to transform one probability distribution into another. While theoretically elegant, the "exact" OT problem is a computationally expensive linear program. The field was revolutionized by entropic regularization—popularized by the Sinkhorn algorithm—which makes OT fast and differentiable. However, entropic regularization has a significant drawback: it produces "blurry" transport plans where every source point is connected to every target point, destroying the sparse, one-to-one structure of the original problem.

A growing body of research suggests that we can maintain the computational benefits of regularization while recovering true sparsity by swapping the entropic penalty for quadratic or $f$-divergence regularizers.

The Blur of Entropic Regularization

To understand why sparsity matters, we must look at how regularization changes the transport plan. In standard OT, we seek a coupling matrix that minimizes cost. Entropic regularization adds a penalty based on the Kullback-Leibler (KL) divergence. Because the derivative of the KL divergence involves an exponential function, the resulting transport plan is strictly positive everywhere.

As noted by Marcel Nutz and Alberto González-Sanz in Sparsity of Quadratically Regularized Optimal Transport: Scalar Case, this "blurring" effect is problematic for tasks like image morphing or document alignment, where we expect a point in the source to map to only one or a few points in the target. Entropic methods spread mass globally, leading to numerical instability when the regularization parameter is small and poor interpretability in high-fidelity applications.

Inducing Sparsity with Quadratic Penalties

The most prominent alternative is quadratic regularization, which replaces the entropic penalty with an $L_2$ norm on the transport plan. This design choice fundamentally changes the geometry of the solution.

The intuition lies in the proximal operator of the regularizer. While the exponential map of entropic OT never reaches zero, the quadratic penalty acts like a "hinge." When the cost of transporting mass between two points exceeds a certain threshold, the regularized objective finds it more optimal to set that transport value to exactly zero.

Marcel Nutz demonstrates in Quadratically Regularized Optimal Transport: Existence and Multiplicity of Potentials that for a sufficiently small regularization parameter $\varepsilon$, the support of the regularized solution remains localized within a narrow "tube" around the true optimal map. This localization ensures that the solution remains sparse even in continuous settings.

The Mechanism of Clipping

The emergence of sparsity is not unique to quadratic penalties; it is a property of a broader class of $f$-divergences. Dávid Terjék and Diego González-Sánchez show in Optimal transport with f-divergence regularization and generalized Sinkhorn algorithm that regularizers like Chi-squared divergence or Tsallis entropy naturally produce sparse plans.

The mathematical "trigger" for this sparsity is the derivative of the regularizer's convex conjugate. If this derivative reaches zero at a finite value, the optimization process "clips" small transport values to zero. This pruning mechanism allows for:

  1. Memory Efficiency: Sparse matrices are significantly cheaper to store than the dense tensors produced by Sinkhorn.
  2. Finite Convergence: Unlike entropic OT, which only reaches the exact solution as $\varepsilon \to 0$, quadratically regularized linear programs can reach the exact, minimal-norm solution at a finite value of $\varepsilon$, as proven in Quantitative Convergence of Quadratically Regularized Linear Programs.

Structured Sparsity for Domain Adaptation

Sparsity is not just about zeroing out noise; it can be used to enforce structural priors. In unsupervised domain adaptation, we often want to ensure that samples from the same class in the source domain are mapped to the same cluster in the target domain.

Ashkan Panahi and colleagues introduce Sum-of-Norms (SON) regularization in Stochastic Proximal Algorithms with SON Regularization. By applying a group-sparsity penalty to the transport plan, they force the transport vectors of similar points to become identical. This mechanism effectively discovers latent block structures in the data, ensuring that class consistency is preserved during transport without requiring target labels.

Similarly, in Quadratically Regularized Optimal Transport on Graphs, Justin Solomon leverages the relationship between the dual problem and the graph Laplacian to develop fast Newton-type solvers that preserve the sparsity of the underlying graph network.

Overcoming the Curse of Dimensionality

A long-standing critique of sparse OT was that it might suffer more severely from the "curse of dimensionality" than its entropic counterpart. However, recent theoretical breakthroughs by Alberto González-Sanz and Marcel Nutz in Sparse Regularized Optimal Transport without Curse of Dimensionality suggest otherwise.

They prove that for a wide class of sparse regularizers, the empirical cost and dual potentials converge at a parametric rate ($n^{-1/2}$) that is independent of the dimension. This statistical stability arises because the linearized dual operator remains invertible even when the coupling is sparse, providing a rigorous foundation for using sparse OT in high-dimensional machine learning tasks.

Papers in this version

Showing 60 of 86 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 82 papers
  2. Version 1 · 2026-10-04 · 86 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_sparse_optimal_transport_bb50718d,
  title = {sparse optimal transport},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sparse-optimal-transport/rdr_bb50718d33ae445fb74b82223176211e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sparse_optimal_transport_via_quadratic_a_bb50718d_v1,
  title = {Sparse Optimal Transport via Quadratic and f-Divergence Regularization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sparse-optimal-transport-via-quadratic-and-f-divergence-regularization/rdr_bb50718d33ae445fb74b82223176211e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}