Why does the distance matrix computed in the optimal transport linear programming model always look the same (asides from its size changing with the number of histogram bins) no matter how the source and target distributions might change?
If we really are supposed to be interested in the distances between samples in the source and target distributions, why does optimal transport dumb down this step to a distance comparison of cardinality, that is, the distances between the integer-indices of the source and target distributions, without any imputation of actual sample observations or probabilities?
Matrix D in the image below is the distance matrix, which always shows the same pattern regardless which sample data is thrown in the model:
Best Answer
The matrix $D$ is completely independent from the input distribution, and element $D_{ij}$ defines how hard it is to move one unit of whatever you are moving from location $i$ to location $j$.
The source and target distributions indicate how much should be moved from and to each location. If you decide to move $0.2$ from location $i$ to location $j$, the contribution to the objective function is $0.2D_{ij}$. Let $s_i$ be the amount available at source location $i$, then the contribution of that amount to the objective function is $\sum_j D_{ij} x_{ij}$ where $x_{ij}$ satisfies $\sum_j x_{ij} = s_i$. Therefore, if $s_i$ is large, row $i$ of matrix $D$ is multiplied with (at least some) large coefficients, so this is how cardinality comes into play.