ott
ott copied to clipboard
univariate dual vectors for arbitrary sizes
this PR implements an extension of the univariate solver that outputs dual vectors, regardless of input sizes / weights.
the implementation uses a lineax sparse solver, instead of going through a manually coded Gauss-seidel loop as in e.g. Alg. 1 of https://arxiv.org/pdf/2201.00730.pdf
the linear system is mostly build by looking at transported mass (returned by the primal solver) and inverting the corresponding linear system.
at the moment, i still observe a bug for the (arguably) least interesting case when comparing two univariate distributions of the same size (in the test, when weight vectors associated to both x
and z
are unif_n
for instance). note this was the case that the https://arxiv.org/abs/2206.07630 paper was dwelling a bit deeper into, but with a quadratic iteration.
note: it might be interesting to actually code the Alg. 1 of https://arxiv.org/pdf/2201.00730.pdf loop with single entry updates and see if it does run faster than this iterative solver.