LogSumExp

The LogSumExp (LSE) function is a smooth approximation to the maximum function, mainly used by machine learning algorithms. It's defined as the logarithm of the sum of the exponentials of the arguments:

$LSE(x_{1},\dots ,x_{n})=\log \left(\exp(x_{1})+\cdots +\exp(x_{n})\right)$

The LogSumExp function domain is $\mathbb {R} ^{n}$, the real coordinate space, and its range is $\mathbb {R}$, the real line. The larger the values of $x_{k}$ or their deviation, the better the approximation becomes. The LogSumExp function is convex, and is strictly monotonically increasing everywhere in its domain (but not strictly convex everywhere ).

On the otherhand, when directly encountered, LSE can be well-approximated by $\max {\{x_{1},\dots ,x_{n}\}}$, owing to the following tight bounds.

$\max {\{x_{1},\dots ,x_{n}\}}\leq LSE(x_{1},\dots ,x_{n})\leq \max {\{x_{1},\dots ,x_{n}\}}+\log(n)$

The lower bound is met when only one of the argument is non-zero, while the upper bound is met when all the arguments are equal.

log-sum-exp trick for log-domain calculations

The LSE function is often encountered when the usual arithmetic computations are performed in log-domain or log-scale.

Like multiplication operation in linear-scale becoming simple addition in log-scale; an addition operation in linear-scale becomes the LSE in the log-domain.

A common purpose of using log-domain computations is to increase accuracy and avoid underflow and overflow problems when very small or very large numbers are represented directly (i.e. in a linear domain) using a limited-precision, floating point numbers.

Unfortunately, the use of LSE directly in this case can again cause overflow/underflow problems. Therefore, the following equivalent must be used instead (especially when the accuracy of the above 'max' approximation is not sufficient). Therefore, many math libraries such as IT++ provide a default routine of LSE and use this formula internally.

$LSE(x_{1},\dots ,x_{n})=x^{*}+\log \left(\exp(x_{1}-x^{*})+\cdots +\exp(x_{n}-x^{*})\right)$

where $x^{*}=\max {\{x_{1},\dots ,x_{n}\}}$

References

• Nielsen, Frank; Sun, Ke (2016). "Guaranteed bounds on the Kullback-Leibler divergence of univariate mixtures using piecewise log-sum-exp inequalities". arXiv:1606.05850.