The incremental log-sum-exp trick

Often in machine learning it is necessary to compute the following quantity. We have a $n$-dimensional vector $\mathbf x$—usually log-probabilities— and we want to calculate:

$$y = \log \sum_{i=1}^n \exp^{x_i}.$$

Calculating the quantity in a naive manner we can encounter underflows or overflows. For an arbitrary $a$, we can shift the center of the exponential sum in the following way:

$$\log \sum_{i=1}^n \exp^{x_i} = a + \log \sum_{i=1}^n \exp^{x_i-a}.$$

A typical value for $a$ is setting it to the maximum, $a = \max_{1\leq i \leq n} x_i$, thus forcing the greatest value to be zero.

However, if the values are available in an incremental way we cannot compute the maximum value. The alternative incremental log-sum-exp trick can be computed using the following recurrence:

$$a_0 = x_0, \\ z_0 = 1, \\ y_0 = x_0,$$

hence, for each $t=1,\ldots, n$, if $x_t > a_{t-1}$ then:

$$z_t = z_{t-1} \exp^{a_{t-1} - x_t} + 1, \\ a_t = x_t, \\ y_t = a_t + \log z_t$$

otherwise,

$$z_t = z_{t-1} + \exp^{x_t - a_{t-1}}, \\ a_t = a_{t-1}, \\ y_t = a_t + \log z_t.$$