ott icon indicating copy to clipboard operation
ott copied to clipboard

univariate dual vectors for arbitrary sizes

Open marcocuturi opened this issue 11 months ago • 0 comments

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.

marcocuturi avatar Mar 23 '24 07:03 marcocuturi