Efficiently summing log quantities

Question

Working in C++, I'd like to find the sum of some quantities, and then take the log of the sum:

log(a_1 + a_2 + a_3 + ... + a_n)

However, I do not have the quantities themselves, I only have their log'd values:

l_1 = log(a_1), l_2 = log(a_2), ... , l_n = log(a_n)

Is there any efficient way to get the log the sum of the a_i's? I'd like to avoid

log(s) = log(exp(l_1) + exp(l_2) + ... + exp(l_n))

if possible - exp becomes a bottleneck as the calculation is done many times.

Answer 1

How large is n?

This quantity is known as log-sum-exp and Lieven Vandenberghe talks about it on page 72 of his book. He also has an optimization package which uses this operation, and from a brief look, it seems as if he doesn't do anything special there, just exponentiates and adds. Perhaps exponentiation is not a serious bottleneck when n is small enough for the vector to fit into memory.

This operation often comes up in modeling and the bottleneck there is the sheer number of terms. Magnitude of n=2^100 is common, where the terms are implicitly represented. In such cases, there are various tricks to approximating this quantity relying on convexity of log-sum-exp. The simplest trick -- approximate log(s) as max(l1,l2,....,ln)