Solve the optimal L2 assignment between data and grid. — optimal

Computes the bijection \(\pi\) between the n sample points and the n grid points that minimizes \(\sum_i \|Z_i - grid_{\pi(i)}\|^2\). This is solved as an optimal transport problem (network-flow solver from the transport package), which is substantially faster than the Hungarian algorithm implemented in clue::solve_LSAP. Used by center_outward_transform to assign each observation its rank on the grid built by build_ball_grid.

Usage

optimal_assignment(Z, grid)

Arguments

Z: Numeric matrix (n x d): Euclidean data.
grid: Numeric matrix (n x d): target grid, e.g. from build_ball_grid.

Value

Integer vector of length n: the grid row assigned to each row of Z.

Examples

Z <- matrix(rnorm(20), nrow = 10, ncol = 2)
grid <- build_ball_grid(n = 10, d = 2, nR = 3, nS = 3, n0 = 1)
optimal_assignment(Z, grid)
#>  [1] 10  6  2  5  7  8  1  3  9  4