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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.