Gaussian filtering is popular in applications, for my question it can be written as (I've fixed the size of window):
$$y_i = \sum_{j = 1}^{n} x_j e^{(i - j)^2}, \qquad i = 1, 2, ..., n $$
One can implement this operation (computing y for given x) via FFT in $n \log(n)$ operations.
The question I am interested: is $n \log(n)$ really a limit? If yes, how can I prove this? If not - how do I write a faster implementation?
Example If I had laplacian kernel instead of gaussian, $$y_i = \sum_{j = 1}^{n} x_j e^{|i - j|}, \qquad i = 1, 2, ..., n, $$ I would be able to compute this in $O(n)$ operations.
