# Filter design to realize Cauchy product

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.

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

• 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.