Optimal Transport (OT) is the mathematical gold standard for comparing probability distributions, but it has long been haunted by the "curse of dimensionality" and a "super-cubic" computational wall. To find the most efficient way to move mass from one distribution to another, standard solvers must compute a transport plan—a massive $n \times n$ matrix that describes how much mass moves from every point in the source to every point in the target.
As datasets in genomics, computer vision, and graph learning scale to millions of points, storing and optimizing this $O(n^2)$ matrix becomes impossible. The research direction of Low-Rank Optimal Transport solves this by fundamentally rethinking the structure of the transport plan, reducing the complexity from cubic or quadratic to linear.
The Quadratic Wall and the Factorization Solution
The traditional Sinkhorn algorithm relies on entropic regularization to make OT solvable, but it still requires $O(n^2)$ operations per iteration because it must repeatedly multiply vectors by a full-sized kernel matrix.
The core intuition behind the low-rank revolution is that we don't actually need to know the individual "path" for every single atom of mass. Instead, we can assume the transport plan has a latent structure. Meyer Scetbon, Marco Cuturi, and Gabriel Peyré demonstrated in Low-Rank Sinkhorn Factorization that by constraining the transport coupling matrix $P$ to have a low nonnegative rank $r$, we can factorize it into $P = Q R^T$, where $Q$ and $R$ are much smaller matrices of size $n \times r$.
This factorization changes the game:
- Memory: Instead of storing $n^2$ entries, we only store $2nr$ entries.
- Speed: Matrix-vector multiplications that previously took $O(n^2)$ time now take $O(nr)$ time. Since $r$ is typically a small constant (e.g., 10 or 100), the algorithm effectively scales linearly with the number of data points.
Why Low-Rank Works: Geometry and Clustering
Why is it physically reasonable to assume a transport plan is low-rank? In many real-world datasets, points aren't scattered randomly; they live on low-dimensional manifolds or form clusters.
In Transport Clustering: Solving Low-Rank Optimal Transport via Clustering, Henri Schmidt and Benjamin Raphael provide the intuition that low-rank OT is mathematically equivalent to a generalized $K$-means clustering problem. The low-rank factors act as "anchors" or "centroids." Instead of mapping every cell to every other cell in a biological atlas, the algorithm maps cells to a small set of latent states, and then maps those states to the target distribution.
This geometric simplification is what allows tools like Moscot, developed by Dominik Klein, Marius Lange, and Giovanni Palla, to align millions of single cells across time and space. As detailed in Mapping cells through time and space with moscot, using low-rank approximations allows these massive biological "atlases" to be processed on standard consumer hardware rather than supercomputers.
Linear-Time Gromov-Wasserstein
The most significant breakthrough in this area involves the Gromov-Wasserstein (GW) distance, which compares datasets that live in different metric spaces (e.g., matching a 3D shape to a 2D image). Standard GW is notoriously expensive, scaling at $O(n^3)$ or even $O(n^4)$.
In Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs, the authors show that if both the coupling (the mapping) and the cost matrices (the internal distances within each dataset) are treated as low-rank, the entire GW objective can be solved in linear time. This is possible because many common cost functions, like squared Euclidean distance, are naturally low-rank. By exploiting this "double factorization," researchers can now align graphs and high-dimensional distributions with millions of points—a task previously considered computationally prohibitive.
Approximating the Kernel: The Nyström Method
Another facet of this direction involves approximating the interaction kernel itself rather than the final transport plan. Jason Altschuler, Francis Bach, and Alessandro Rudi demonstrated in Massively scalable Sinkhorn distances via the Nyström method that one can sample a small subset of columns from the cost matrix to represent the full interaction space.
This Nyström-based approach provides a "shortcut" to the Sinkhorn iterations. By performing the iterative scaling directly on these sampled factors, the memory footprint remains linear. This technique is particularly powerful for "zero-shot" model selection in AutoML, where frameworks like LOTUS, proposed by Joaquin Vanschoren and Prabhant Singh, use low-rank OT to instantly compare a new dataset against a library of thousands of historical ones to recommend the best algorithm (AutoML for Outlier Detection with Optimal Transport Distances).
Beyond Speed: A New Kind of Regularization
It is tempting to view low-rank OT merely as a "fast version" of the original. However, as Meyer Scetbon argues, low-rank constraints provide a different, often more desirable, form of regularization than entropic smoothing.
While entropic Sinkhorn tends to "blur" the transport plan everywhere, low-rank factorization forces the transport to flow through a small number of "bottlenecks." This often results in cleaner, more interpretable alignments in tasks like brain mesh alignment (Unbalanced Low-rank Optimal Transport Solvers) and generative modeling (Transport Based Mean Flows for Generative Modeling), where enforcing geometric structure is more important than achieving the absolute minimum mathematical cost.