Timeline for Optimal transport: find cost function given observed transport
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 5, 2021 at 20:37 | comment | added | JHM | Look again at the inequality $-\phi(x)+\psi(y)\leq c(x,y)$ for all $x\in X$, $y\in Y$. If $h(x,y)$ is any function satisfying $-\phi(x)+\psi(y)\leq c(x,y)+h(x,y)$ for all $x,y$ and obtains equality iff $(x,y)\in spt(\pi)$, then the new cost $c':=c+h$ will again have $\pi$ as $c'$-optimal transport (... if i'm not mistaken). | |
| Jan 5, 2021 at 19:55 | comment | added | JHM | It is strange question, for if the $c$-optimal coupling $\pi$ is observable, then are the dual Kantorovich potentials $-\phi=\psi^c$, $\psi^{cc}=\psi$ also observable? For we have always $-\phi(x)+\psi(y)\leq c(x,y)$ for all $x\in X$, $y\in Y$ with equality iff $x\in \partial^c \psi(y)$ iff $y\in \partial^c \phi(x)$ iff $(x,y)\in spt(\pi)$. Therefore if $\phi, \psi$ are observable, then you have pointwise lower bound for $c(x,y)$, namely $-\phi(x)+\psi(y)$ for arbitrary $x,y$. All the above answers show the problem is underdetermined, with many arbitrary parameters. | |
| Oct 28, 2020 at 8:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jun 30, 2020 at 7:05 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| May 31, 2020 at 6:25 | history | edited | Martin Sleziak |
added a top-level tag; see: https://meta.mathoverflow.net/questions/1457/why-are-mo-tags-formatted-as-they-are
|
|
| May 31, 2020 at 6:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| May 1, 2020 at 4:56 | answer | added | Piyush Grover | timeline score: 1 | |
| May 1, 2020 at 0:19 | comment | added | leo monsaingeon | @Gabe K: good point! | |
| May 1, 2020 at 0:06 | comment | added | Will Sawin | If both functions are supported on a finite space, and you demand that the cost function be a metric, it should suffice that the transport map has no loops where $A$ is sent to $B$, $B$ is sent to $C$, and $C$ is sent to $A$, or whatever. Indeed, in this case, the transport map induced a partial order, which you can complete to a total order, and then take the cost to be the number of steps in the total order | |
| May 1, 2020 at 0:02 | comment | added | Will Sawin | By Lagrange multipliers, such cost functions have the form $C(x,y) =a(x) +b(y)+ c(x,y)$ where $c$ is nonnegative everywhere and $0$ on the support of the transport map. If you're asking for functions that satisfy linear conditions and inequalities such as being a metric, or strict convexity as suggested by Leo, then finding a suitable cost function is a linear programming problem. | |
| May 1, 2020 at 0:00 | comment | added | Gabe K | To add another complication, in one dimension for any cost of the form $c(x,y)=h(x-y)$ for $h$ convex, the solution to optimal transport will be the identical, and is given by the so-called monotone map. | |
| Apr 30, 2020 at 23:52 | comment | added | leo monsaingeon | Even with regularity enforced you should not expect uniqueness, at least not for a single "observation". For, you can always add a (smooth) non-negative function vanishing on $spt(\pi)$, at least when this support is smooth. So I guess it's more about requiring "structure", really (e.g. strict convexity, twist conditions, etc...) I'm sorry I can't help you more, I've never heard of such a problem. | |
| Apr 30, 2020 at 23:44 | comment | added | Sergey Egiev | Thanks! Yes, I agree that the space of functions should be restricted (and may be with very stringent requirements to get uniqueness). I am looking for a systematic study of this. | |
| Apr 30, 2020 at 23:33 | comment | added | leo monsaingeon | Well, one probably needs further regularity requirements on the cost function, otherwise $c(x,y)=0$ for all $(x,y)\in spt(\pi)$ and $c(x,y)=+\infty$ otherwise trivially does the job ($\pi$ being the transference plan) | |
| Apr 30, 2020 at 23:04 | review | First posts | |||
| Apr 30, 2020 at 23:40 | |||||
| Apr 30, 2020 at 23:03 | history | asked | Sergey Egiev | CC BY-SA 4.0 |