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?
