Optimal Transport

The original formulation of Optimal Transport seeks a deterministic mapping T that pushes forward a source distribution μ to a target distribution ν while minimizing the total transportation cost. The objective is to find T such that for each point x, T(x) specifies its unique destination, minimizing ∫ c(x, T(x))dμ(x). This formulation is non-convex and may not admit a solution, particularly when mass needs to be split—a limitation that motivated Kantorovich's relaxation.

Kantorovich generalized the Monge problem by allowing probabilistic coupling through a joint distribution π (the transport plan) with marginals μ and ν. Instead of a deterministic map, mass at x can be split across multiple destinations. The problem becomes a linear program: minimize ∫∫ c(x,y)dπ(x,y) over all couplings π. This convex relaxation guarantees existence and uniqueness under mild conditions, making it computationally tractable for modern applications like domain adaptation and single-cell alignment.

The minimal cost achieved by the optimal transport plan defines the Wasserstein distance (Earth Mover's Distance) between distributions. For p≥1, the p-Wasserstein distance is W_p(μ,ν) = (inf ∫∫ ||x-y||^p dπ(x,y))^(1/p). Unlike f-divergences (KL, JS), the Wasserstein distance:

• Respects the underlying geometry of the space
• Provides meaningful gradients even when distributions have disjoint supports
• Is a true metric satisfying symmetry and triangle inequality This makes it the preferred loss function in Wasserstein GANs and single-cell trajectory inference.

Computing exact Optimal Transport scales as O(n³ log n) for discrete distributions with n points, making it prohibitive for large-scale single-cell datasets. Entropic regularization, introduced by Cuturi (2013), adds an entropy term -εH(π) to the objective, making the problem strictly convex and solvable via the Sinkhorn algorithm in O(n²) time. The parameter ε controls the trade-off:

• Small ε: Sharp, sparse transport plans approximating exact OT
• Large ε: Diffuse, smoother plans with faster convergence This breakthrough enabled OT to scale to modern single-cell atlases with millions of cells.

The Gromov-Wasserstein (GW) distance extends OT to compare distributions defined on different metric spaces by comparing pairwise distances within each domain rather than cross-domain distances. Given distributions on spaces X and Y with distance matrices d_X and d_Y, GW finds a coupling that preserves intrinsic relational structure. In single-cell biology, GW enables:

• Aligning cells across different species where gene orthologs differ
• Integrating different omics modalities (scRNA-seq to scATAC-seq) without shared features
• Matching developmental trajectories across experimental conditions by comparing cellular similarity graphs

Classical OT requires exact mass conservation: the total mass of source and target distributions must be equal. Unbalanced Optimal Transport relaxes this constraint by allowing mass creation and destruction through divergence penalties (e.g., KL divergence) on the marginals. This is critical for single-cell applications where:

• Cell populations may proliferate or die between time points
• Technical dropout in scRNA-seq creates spurious zero counts
• Different samples contain varying cell-type proportions Unbalanced OT formulations, such as the Wasserstein-Fisher-Rao distance, handle these realistic biological scenarios by jointly optimizing transport and mass variation.

The Earth Mover's Distance quantifies the minimal cost to transform one probability distribution into another. In single-cell biology, it serves as a robust metric for comparing cell populations, measuring the dissimilarity between two samples by calculating the optimal transport plan. Unlike KL-divergence, it respects the underlying geometry of the gene expression space.

• Key Property: Satisfies metric axioms (symmetry, triangle inequality)
• Application: Quantifying differentiation trajectories between time points
• Advantage: Remains stable even when distributions have non-overlapping support

An entropically regularized approximation of the classic optimal transport problem that makes computation tractable for high-dimensional biological data. By adding an entropy penalty to the transport plan, the Sinkhorn algorithm enables GPU-accelerated, differentiable OT solvers.

• Mechanism: Iteratively normalizes rows and columns of a kernel matrix
• Benefit: Reduces computational complexity from O(n³ log n) to O(n²)
• Use Case: Aligning thousands of single cells across batches in seconds

An extension of optimal transport that compares distributions residing in incomparable metric spaces. It aligns datasets by preserving intra-domain pairwise distances rather than requiring a pre-defined cross-domain cost function.

• Multi-Omics Application: Matching cells profiled with scRNA-seq to cells profiled with scATAC-seq where feature spaces differ
• Mechanism: Minimizes the distortion of pairwise similarity structures
• Output: A soft mapping that identifies corresponding cellular states across modalities

The foundational mathematical formulation that transforms the Monge problem into a convex linear programming task. Instead of seeking a deterministic map, it solves for a probabilistic coupling matrix that allows mass splitting.

• Formulation: Finds a joint distribution with prescribed marginals minimizing expected cost
• Dual Form: Enables the use of Kantorovich potentials for adversarial training
• Biological Relevance: Models the stochastic nature of cellular state transitions

A relaxed formulation that allows for the creation and destruction of mass during transport, accommodating differences in total cellular abundance. This is critical for comparing samples with varying cell counts or when certain populations proliferate or die off.

• Divergence: Uses Csiszár divergences instead of hard marginal constraints
• Application: Modeling cell proliferation and apoptosis in developmental time courses
• Parameter: A relaxation coefficient controls the penalty for mass variation