Filter design to realize Cauchy product

Question

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.

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.