Monday, May 19, 2014

Logarithm of A Sum of Exponentials: Part 1

Problem: Consider a stream of real numbers $x_1, x_2, ..., x_N$. We don't know the magnitude or sign of these numbers.

We want to numerically compute the following sum, for arbitrary $x_i$ ,$F = \log \left(e^{x_1} + e^{x_2} + ... + e^{x_N} \right).$

Motivation: Versions of this problem occur in many places. In statistical mechanics, for example, $x_i = -\beta U_i$ might correspond to the energy of the system, normalized by the Boltzmann factor.

The logarithm of the partition function $Z = \sum e^{x_i}$, corresponds to a free energy, $F = \log Z$.

Issue: The central issue at stake here can be articulated by considering a single term of the summation. $F = \log e^{x_1} = x_1.$ Suppose $x_1$ was 1000. Numerically computing $\log e^{1000}$ would be a problem, because $e^{1000}$ is greater than the largest number (~ $10^{308}$)that can be represented in double precision.