ot.bsp

Efficient combinatorial optimization for low transport cost bijections based on Binary Space Partitioning trees (BSP-OT).

ot.bsp.compute_bspot_bijection(X, Y, n_plans=64, p=2, initial_perm=None, gaussian_slicing='auto', seed=0)[source]

This solver provides a good and fast approximation of the combinatorial problem of finding a bijection between two point clouds that minimizes the transport cost:

\[\min_{\sigma \in S_n} \sum_{i=1}^n \|X_i - Y_{\sigma(i)}\|_p^p\]

To do so, it generates \(n_{plans}\) random bijective BSP matchings, merges them together to obtain a bijection of low transport cost. Log-linear complexity in the number of points. Algorithm 2 & 3 from [84].

Note

There is no guarantee on the quality of the returned bijection, but the method is highly scalable on the CPU. Worst cases are obtained between point clouds that are very similar (e.g. two samples from the same distribution), where the solver can get stuck in local minima, but works well when the point clouds are very different. The method also works best for the standard squared euclidean cost (p=2), as this cost enables efficient BSP construction heuristic (with a cubic dependence on the dimension, this feature is disabled for dimensions larger than 64).

Parameters:

  • X (array-like, shape (n_samples, dimension))

  • Y (array-like, shape (n_samples, dimension))

  • n_plans (int) – The number of BSP Matchings used to compute the final bijection.

  • p (int, optional) – The power of the ground metric (default 2 for squared euclidean, -1 for infinity norm).

  • initial_perm (array-like, shape (n_samples,), optional) – Bijection to use for initializing merging (optional).

  • gaussian_slicing ("auto" or bool, optional) – If true then uses the Gaussian slicing heuristic to improve matching quality. Comes with a cubic complexity with dimension. If ‘auto’, then the heuristic is used for dimensions smaller than 64, and disabled for larger dimensions.

  • seed (int, optional) – Random seed for reproducibility (default 0).

Returns:

  • cost (float) – The transport cost of the final bijection.

  • perm (array-like, shape (n_samples,)) – The final bijection, stored as a permutation (e.g. a list of numbers) such that X[i] is assigned to Y[perm[i]].

  • perms (array-like, shape (n_plans,n_samples)) – The intermediary bijections used to compute the final one.

ot.bsp.merge_bijections(X, Y, perms, p=2)[source]

Merge several bijections between two point clouds to obtain a new one with low transport cost. The new bijection is guaranteed to have a transport cost no greater than the cost of any of the input bijections. Based on simple local/global swapping strategy, with a linear complexity in the number of points. Algorithm 3 from [84].

Parameters:

  • X (array-like, shape (n_samples, dimension))

  • Y (array-like, shape (n_samples, dimension))

  • perms (array-like, shape (n_plans,n_samples)) – The bijections to merge, stored as permutations (e.g. a list of numbers)

  • p (int, optional) – The power of the ground metric (default 2 for squared euclidean). If p is -1, the infinity norm is used.

Returns:

  • cost (float) – The transport cost of the merged bijection.

  • perm (array-like, shape (n_samples,)) – The merged bijection, stored as a permutation (e.g. a list of numbers) such that X[i] is assigned to Y[perm[i]].