Spatial-omics technologies measure thousands of molecular features, such as gene expression, at tens to hundreds of thousands of locations in a tissue. Aligning such datasets across tissue slices or developmental time points is naturally posed as an optimal transport (OT) problem, with relaxed marginals to account for cell growth and death. At these scales, the quadratic size of the transport plan makes standard solvers infeasible.

I will describe two algorithms we have developed for these applications. The first computes low-rank transport plans through a latent-coupling factorization that splits the problem into three simpler OT subproblems, yielding a linear-space algorithm. The second, Hierarchical Refinement, rests on the observation that optimal low-rank couplings co-cluster each point with its image under the Monge map. This yields a recursive algorithm that computes a full-rank bijective map in log-linear time and linear space, scaling to over a million points. I will demonstrate these algorithms on spatiotemporal transcriptomics data from embryonic development.

This is joint work with: Peter Halmos, Julian Gold, Xinhao Liu, and Henri Schmidt