3
$\begingroup$

I want to compute an expression of the form:

$$L = \ln\sum_i e^{x_i}$$

Suppose that there are many small terms, say $e^{x_i} \approx \epsilon$. If there are $N_\epsilon$ such terms, their contribution to the sum is $\approx \epsilon N_\epsilon$.

In the usual logsumexp trick, we let $a=\max x_i$ and compute

$$L = a + \ln \sum_i e^{x_i - a}$$

to avoid overflows. However, $\epsilon$ could be so small that $\epsilon / e^a$ becomes zero in floating-point (underflow). Even then, if $N_\epsilon$ is large enough, a significant contribution $\epsilon N_\epsilon$ to the sum will be lost.

How to deal with this case? A priori I may not know about the existence of these very small terms in the sequence. Applying the logsumexp trick in this case may lead to large errors. Is there a better algorithm?

$\endgroup$
  • 2
    $\begingroup$ Can you give an example of actual numbers you have in mind where this demonstrably leads to an error? Because (w.l.o.g. $a=0$), if $\epsilon\sim 10^{-308}$ underflows, $N_\epsilon$ would have to be immense for the error to approach a machine epsilon of $10^{-16}$. Also, I want to say that the second formula is a little confusingly stated because one of its terms is guaranteed to be $=1$, so underflow inside the log terms should be harmless due to this estimate. $\endgroup$ – Kirill Aug 4 '16 at 22:33

Your Answer

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

Browse other questions tagged or ask your own question.