The Quadratic Wall of Optimal Transport
Optimal Transport (OT) provides a mathematically rigorous framework for comparing probability distributions by calculating the minimum cost required to transform one distribution into another. However, applying OT to modern, large-scale machine learning problems introduces a severe computational bottleneck.
In its standard formulation, computing the distance between two distributions of size $n$ requires optimizing an $n \times n$ transport plan (or coupling matrix) $\Pi$ against an $n \times n$ cost matrix $C$. As highlighted in a comprehensive survey by Abdelwahed Khamis et al., this traditional formulation scales with a "super-cubic" or quadratic computational complexity. When dealing with modern datasets—such as single-cell genomics atlases containing millions of cells—storing and optimizing these full-rank matrices quickly exhausts hardware memory limits, a challenge discussed by Dominik Klein et al..
To bypass this quadratic wall, a powerful paradigm has emerged: Low-Rank Factorization. By forcing the underlying transport matrices into low-rank structures, the computational and memory complexity drops from quadratic ($O(n^2)$) to linear ($O(n)$).
The Intuition of Low-Rank Couplings
Why can we compress a transport plan without losing its geometric utility? A full-rank coupling matrix $\Pi$ implies that every single source point can interact with every target point in a completely unique, independent way. However, real-world data rarely fills the available space uniformly; it typically concentrates along low-dimensional manifolds or clusters.
Instead of searching the entire quadratic space of possible couplings, we can constrain the transport plan $\Pi$ to have a low nonnegative rank $r$, where $r \ll n$. As introduced by Meyer Scetbon et al. in their Low-Rank Sinkhorn Factorization (LOT) framework, a low-rank coupling matrix can be explicitly factorized into the product of two smaller matrices, $A$ and $B$, connected by a shared marginal:
$$\Pi = A \text{diag}(1/\mu) B^T$$
This factorization changes the optimization landscape. Instead of optimizing $n^2$ parameters, the solver only needs to optimize two matrices of size $n \times r$. Intuitively, this constraint forces the transport plan to route mass through a fixed number of $r$ latent interaction patterns or "hubs" rather than computing point-to-point paths for every pair, reducing the parameter search space significantly (Abdelwahed Khamis et al.). In a subsequent theoretical analysis, Meyer Scetbon et al. proved that this structural constraint also acts as a statistical regularizer, allowing the model to bypass the "curse of dimensionality" that typically degrades empirical transport estimation in high dimensions.
Bypassing the Cost Matrix with Kernel Approximations
Even if the coupling matrix $\Pi$ is factorized, evaluating the transport objective still requires interacting with the $n \times n$ cost matrix $C$ (or its corresponding Gibbs kernel $K = \exp(-C/\epsilon)$ used in entropic Sinkhorn scaling). Constructing this matrix explicitly still costs $O(n^2)$ time and memory.
To achieve true linear-time complexity, the cost or kernel matrix must also be factorized. For certain cost functions, such as squared Euclidean distance, the cost matrix possesses an inherent low-rank structure that can be exploited directly to avoid full matrix construction during iterative updates (Meyer Scetbon et al.).
For more complex or arbitrary cost functions, researchers employ data-dependent low-rank approximations, most notably the Nyström method. Jason M. Altschuler et al. demonstrated that by sampling a small subset of columns from the kernel matrix, the Nyström method can reconstruct a highly accurate low-rank approximation of the full kernel. Storing and manipulating only these landmark columns reduces the computational and memory footprint to linear scaling, enabling entropic optimal transport to scale to millions of data points on standard hardware.
This kernel approximation strategy has proven highly adaptable. It has been integrated into biomedical pipelines to process massive single-cell datasets (Jingyi Zhang et al.), combined with robust transport formulations to mitigate the influence of outliers in linear time (Khang Le et al.), and proposed as a vital scaling mechanism for kernel-based optimal transport in Reproducing Kernel Hilbert Spaces (Qian Li et al.).
Scaling Relational and Unbalanced Transport
The true power of combining low-rank couplings with low-rank costs becomes evident in relational transport problems, such as the Gromov-Wasserstein (GW) distance. GW distances align datasets across entirely different spaces (e.g., matching a 3D shape to a 2D image) by comparing intra-dataset distance matrices. Because it evaluates pairs of pairs, standard GW solvers suffer from a cubic ($O(n^3)$) or even quartic computational complexity.
By applying a dual-factorization strategy—restricting both the transport coupling matrix and the relational cost matrices to low-rank structures—Meyer Scetbon et al. successfully broke this barrier, reducing the complexity of Gromov-Wasserstein distances to linear time. This dual-factorization approach allows the iterative optimization process to scale to massive datasets that were previously completely inaccessible.
Standard OT: [ n x n Coupling ] x [ n x n Cost ] --> O(n²) Memory & Time
Low-Rank OT: [n x r] x [r x n] x [n x r] x [r x n] --> O(nr) Linear Complexity
(Latent Hub Routing) (Nyström Landmark Cost)
This representational strategy has unlocked several advanced applications:
- Unbalanced Transport: Marco Cuturi et al. extended low-rank solvers to unbalanced optimal transport (where mass conservation constraints are relaxed). Their approach maintains high predictive accuracy and linear complexity on high-resolution spatial datasets, such as brain mesh alignments, where traditional entropic solvers fail due to memory exhaustion.
- Graph Alignment: In graph representation learning, Zhichen Zeng et al. leveraged low-rank optimization to approximate Gromov-Wasserstein geodesics. This formulation reduced the complexity of graph alignment from quartic to quadratic, providing a mathematically principled and computationally efficient way to perform data augmentation on complex graph structures.
Key Foundational Work
Low-Rank Sinkhorn Factorization (2021) — contributed 4 concept elements to this direction.
On Robust Optimal Transport: Computational Complexity and Barycenter Computation (2021) — contributed 2 concept elements to this direction.
Massively scalable Sinkhorn distances via the Nyström method (2019) — contributed 2 concept elements to this direction.