0
$\begingroup$

I have a matrix, for example $M = \begin{bmatrix}300&100\\20&5\end{bmatrix}$, and I want to use $e^{-M}$ as a distance function. Computationally, numbers such as $e^{-300}$ are rounded to zero, so I want to transform $M$ into $M'$ with all its elements in $[0,1]$ and the property that the ratio of the negative exponential for any two elements is the same in $M$ and $M'$. For example,$\frac{e^{-300}}{e^{-5}} = \frac{e^{-f(300)}}{e^{-f(5)}}$ where $f \mapsto [0,1]$.

I have tried setting this problem up as finding $f$ s.t. $\frac{e^{-x}}{e^{-y}} = \frac{e^{-f(x)}}{e^{-f(y)}}$ which transforms into $f(x) - x = f(y) - y$. However, I am unsure how to proceed from here.

$\endgroup$
1
  • 1
    $\begingroup$ If you mean that $f : \mathbb{R}_{\ge 0} \to [0, 1]$ is a map such that $x - y = f(x) - f(y)$, then this is impossible because $|f(a) - f(b)|\le1$ for all $a, b \in \mathbb{R}_{\ge 0}$, so $2 = 3 - 1 \ne f(3) - f(1) \le 1$. $\endgroup$
    – dirich1337
    Jun 5, 2020 at 9:46

1 Answer 1

1
$\begingroup$

Correct me if I'm wrong, but I suspect you're trying to implement the Sinkhorn algorithm in a numerically stable way.

In that case you are constructing a kernel $K := e^{-\frac{C}{\varepsilon}}$, where $C$ is some cost matrix and division by a regularization constant $\varepsilon>0$ is meant elementwise.

So if elements in $C$ get large, elements in $K$ get closer to zero and numerically you might get underflows.

One important thing here is that $K$ is not the cost matrix, but $C$ is - and since the absolute cost from one unit of mass to another is not important for our transport problem, but only the relative cost, we can rescale $C$ by some factor, for example divide it by the largest value in $C$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.