# Summation of gaussians

Suppose we have given constants $A_i, x_i (i=1..N)$

Is it possible to approximately calculate the sum of N gaussians in less than N iterations for any x? (may be with some preprocessing)

$$\sum_{i=1}^{N}A_i e^{-(x-x_i)^2}$$

The same question for 2D case $$\sum_{i=1}^{N}A_i e^{-(x-x_i)^2-(y-y_i)^2}$$

• Google (scholar) for "fast gaussian summation" or "fast gauss transform". – Hans Engler Dec 6 '15 at 15:21

## 1 Answer

If the $A_i$, $x_i$ and $y_i$ can take arbitrary values then it is hopeless because you even need $N$ iterations merely to read the input.

If (some of) the Gaussians have the same distribution then their sum can be expressed as a single Gaussian.