I come from Computer Science so please pardon for my possibly wrong terminology.

I need to design a filter which has coefficients $$h_0, h_1, \ldots, h_n, \ldots \quad\text{such that}\quad h_0 > h_1> \ldots > h_n > \ldots$$

The input is $x_n$. The output is $y_n$. The relationship between $h_n$, $x_n$ and $y_n$ is a convolution: $$y_n = h_0 x_n + h_1 x_{n-1} + \ldots + h_n x_0$$

The problem is that I have to carry out a convolution to compute the output $y_n$ upon the arrival of every new input $x_n$. So I have to keep all $x_1, x_2, \ldots, x_n, \ldots$ in memory and do $n+1$ multiplications and $n$ additions every time.

I would like to ask whether there is any way to design the coefficient $h_n$ such that I can compute $y_n$ more efficiently. I know of one solution, which is $h_n=\lambda^n$ with $0<\lambda<1$ but this function decays too fast.

Any idea to approximate this procedure is also welcomed.

  • $\begingroup$ I am curious. What is your application? With $\lambda$ close to $1^-$, well-chosen wrt $n$, $\lambda^k$ may decay slowly $\endgroup$ Feb 28, 2018 at 15:01

1 Answer 1


Apart from filters with exponential decay, and assuming you allowing approximations, the question resides in what does cost

  • if your $h_k$ decay like exponentials, you can fit one or two exponentials to them, and there is a huge image processing literature on fast implementations of Gaussian/exponential filters.
  • if float multiplication costs, you can use coefficients coded as dyadic rationals ($i/2^n$) with $i$ and $n$ integers, or sums thereof (SOPOT: sums of powers of two), with some multiplierless designs.
  • if you can parallelize, one factorization idea is based on the polynomial Horner factorization: $$y_n = h_0 (x_n + h_1/h_0 (x_{n-1} + \ldots + (h_n /h_{n-1}\ldots h_0 x_0)))$$ where the $h_k/\prod h_{k-1}$ could be small (with your monotonic rule) or coded as SOPOTs. I don't know if this has been used elsewhere.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.