Presentation
BSP-OT: Sparse transport plans between discrete measures in loglinear time
DescriptionTo solve the optimal transport problem between two uniform discrete measures of the same size, one seeks a bijective assignment that minimizes some
matching cost. For this task, exact algorithms are intractable for large problems, while approximate ones may lose the bijectivity of the assignment.
We address this issue and the more general cases of non-uniform discrete
measures with different total masses, where partial transport may be desirable. The core of our algorithm is a variant of the Quicksort algorithm
that provides an efficient strategy to randomly explore many relevant and
easy-to-compute couplings, by matching BSP trees in loglinear time. The
couplings we obtain are as sparse as possible, in the sense that they provide
bijections, injective partial matchings or sparse couplings depending on the
nature of the matched measures. To improve the transport cost, we propose
efficient strategies to merge 𝑘 sparse couplings into a higher quality one.
For 𝑘= 64, we obtain transport plans with typically less than 1% of relative
error in a matter of seconds between hundreds of thousands of points in 3D
on the CPU. We demonstrate how these high-quality approximations can
drastically speed-up usual pipelines involving optimal transport, such as
shape interpolation, intrinsic manifold sampling, color transfer, topological
data analysis, rigid partial registration of point clouds and image stippling.
matching cost. For this task, exact algorithms are intractable for large problems, while approximate ones may lose the bijectivity of the assignment.
We address this issue and the more general cases of non-uniform discrete
measures with different total masses, where partial transport may be desirable. The core of our algorithm is a variant of the Quicksort algorithm
that provides an efficient strategy to randomly explore many relevant and
easy-to-compute couplings, by matching BSP trees in loglinear time. The
couplings we obtain are as sparse as possible, in the sense that they provide
bijections, injective partial matchings or sparse couplings depending on the
nature of the matched measures. To improve the transport cost, we propose
efficient strategies to merge 𝑘 sparse couplings into a higher quality one.
For 𝑘= 64, we obtain transport plans with typically less than 1% of relative
error in a matter of seconds between hundreds of thousands of points in 3D
on the CPU. We demonstrate how these high-quality approximations can
drastically speed-up usual pipelines involving optimal transport, such as
shape interpolation, intrinsic manifold sampling, color transfer, topological
data analysis, rigid partial registration of point clouds and image stippling.
Event Type
Technical Papers
TimeWednesday, 17 December 20251:10pm - 1:20pm HKT
LocationMeeting Room S421, Level 4