Research map / Learning theory and algorithms / Optimal transport
Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FRLC, a coordinate mirror descent algorithm over the latent coupling factorization of low-rank optimal transport that decouples the problem into three OT subproblems and handles W, GW, FGW with balanced, unbalanced, and semi-relaxed marginals.
Problem
Computing low-rank optimal transport plans for large datasets, where the full coupling matrix scales quadratically, while supporting multiple OT objectives and relaxed marginal constraints.
Approach
Parameterize low-rank couplings with the latent coupling (LC) factorization P = Q diag(1/g_Q) T diag(1/g_R) R^T, with a general (non-diagonal, possibly non-square) latent coupling T, and optimize it via coordinate mirror descent alternating a semi-relaxed "factor relaxation" step on (Q,R) and a balanced Sinkhorn step on T, so no Dykstra projections or explicit inner-marginal optimization are neede
Key results
- On synthetic two-moons vs eight Gaussians (n=m=1000), FRLC achieves lower transport cost than LOT across all ranks 20-200 and initializations, with about half LOT's CPU runtime at rank 100.
- On spatial transcriptomics alignment (about 30,000 vs 50,000 cells), semi-relaxed FRLC achieves the best results on all three metrics by a large margin over LOT-U and LOT-SR.
- On graph partitioning over 12 dataset/objective settings, FRLC outperforms GWL and SpecGWL on 9/12 and 11/12 of the datasets respectively.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FRLC instead of LOT | balanced low-rank Wasserstein OT · Two moons and eight Gaussians; 2D and 10D Gaussian mixtures | transport cost | Helped |
| Increase FRLC rank | balanced low-rank Wasserstein OT · Two moons and eight Gaussians | transport cost | Helped |
| Use FRLC instead of LOT | balanced low-rank Wasserstein OT · Synthetic datasets, n=m=1000, rank r=100 | runtime: half the runtime | Helped |
| Use FRLC instead of LOT | balanced low-rank Wasserstein OT · Synthetic datasets | marginal error | Helped |
| Use FRLC instead of Latent OT | balanced low-rank Wasserstein OT · Synthetic datasets | primal OT cost | Helped |
| Use FRLC-U instead of LOT-U | unbalanced OT alignment · Spatial transcriptomics alignment | downstream prediction performance | Mixed |
| Relax the marginal using FRLC-SR instead of LOT-SR | semi-relaxed OT alignment · Spatial transcriptomics alignment | downstream prediction performance | Helped |
| Use FRLC instead of GWL and SpecGWL | graph partitioning · Four real-world graph datasets | clustering performance: 9/12 and 11/12 | Helped |
Limitations
- Selecting the latent coupling rank(s) and the tau regularization hyperparameter, which controls trajectory smoothness.
- Sensitivity to initialization due to non-convexity of the objective, and convergence criterion remains non-asymptotic/weak.
- Non-convex objective means only stationary convergence guarantees are provided.
Experimental setup
Datasets: two moons and eight Gaussians synthetic data 10D mixture of Gaussians mouse embryo spatial transcriptomics (E11.5 and E12.5) four real-world graph datasets
Benchmarks: synthetic Wasserstein transport cost spatial transcriptomics gene expression prediction spatial transcriptomics cell type prediction graph partitioning clustering
Metrics: transport cost marginal error Spearman correlation ARI AMI runtime
Baselines: LOT LOT-U Latent OT GWL SpecGWL full-rank OT
Builds on: LOT (low-rank optimal transport) Forrow et al. 2019 factored couplings Latent OT (Lin et al.) Sinkhorn algorithm GWL
Closest papers by meaning
- Hierarchical Refinement: Optimal Transport to Infinity and Beyond (ICML 2025 · similarity 0.90)
- Sparsistency for inverse optimal transport (ICLR 2024 · similarity 0.88)
- Expected Sliced Transport Plans (ICLR 2025 · similarity 0.88)
- Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation (NeurIPS 2026 · similarity 0.88)
- Progressive Entropic Optimal Transport Solvers (NeurIPS 2024 · similarity 0.87)
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.