Optimal transport problem (is it?) for moving unequal number of samples

[ogencoglu]

I am trying to find the minimum cost of moving source samples in 2D to target samples so that all target samples are covered and all source samples do not need to be moved. Is this falling under optimal transport at all or is this some sort of assignment problem (Hungarian algorithm etc.)?

For example adjusting your 20 sample vs 20 sample examples here: https://pythonot.github.io/auto_examples/plot_OT_L1_vs_L2.html

I want to find the minimum cost (let's say euclidean) of covering the 7 target samples using the 20 source samples in however way.

I expect 13 samples to be unmoved (because 7 is enough) but here is the result:

Can I achieve this with POT?

[ogencoglu]

Any guidance @rflamary @SoniaMaz8 @cedricvincentcuaz @eloitanguy @matthewfeickert @clbonet ?

[eloitanguy]

Hi, this is a variant of Partial OT, see https://pythonot.github.io/gen_modules/ot.partial.html#id34
Partial OT imposes the movement of a mass m, so it is not precisely what you need. To my knowledge this is the closest available function for your needs.

[ogencoglu]

Thanks for the guidance. Do I understand correctly that partial OT solves the reverse problem of my question above: "exactly m samples need to be moved" instead of my question of "exactly m target samples need to be covered"? I guess I can achieve what I want by switching the source<->target.

[rflamary]

if you force a mass m to be transported and your weights on the sampels are equal to one then at leats m saples will be moved (with all or part of their mass moved). To force exactly m sampls is an integer programming problem so much more difficult to solve (and out of scope of POT).

[eloitanguy]

Not exactly. The partial problem is symmetrical in source/target, it enforces the total amount of mass moved between source and target. Mass is more precise than "amount of samplea" it is related to the weight vectors a and b you place on your samples. The mathematical problem behind the partial OT formulation in https://pythonot.github.io/gen_modules/ot.partial.html#id34 conveys this more formally.
For you case, if the source has more mass than the target (say mass 1 on each of the n source sample), you could ask the problem to move the total amount of mass of the target (with for instance mass 1 on the m<n target samples), thus enforcing all target samples to be reached my the coupling.