Deconvolve a FIR-filter using limits? Or: Are limits distributive with the inverse fourier transform?

Question

Given $y[n] = f[n] * h[n]$ where $y[n]$ and $f[n]$ are two one-dimensional discrete signals that are given, find out:

• if $h[n]$ is a FIR-filter
• if it is a FIR-filter, what its kernel is.

Obviously, this can be done by doing deconvolution: $h[n] = y[n] *^{-1} f[n]$. Performing deconvolution (written here as $*^{-1}$) in the time domain is of course computationally expensive. However, it is possible to go to the frequency-domain instead:

$$h[n] = y[n] / f[n] = \mathcal{F^{-1}}(Y ./ F) $$ (Where $ ./$ is pairwise division and $Y$ and $F$ are the (discrete) fourier transformations of $y[n]$ and $f[n]$ respectively, that is $Y = \mathcal{F}(y[n]$), $F = \mathcal{F}(f[n])$).

Many existing algorithms use this property, since pairwise division has a lower time-complexity) than direct deconvolution.

However, these algorithms claim to struggle with zero-valued frequencies: If $F$ contains a zero, then we will divide by zero during the pairwise division.

My question is: Is it possible to calculate the outcomes using limits here? After all:

\begin{align} \lim_{k\to 0^+} \frac{x}{k} &= \lim_{l\to \infty} l \tag{$0^+$}\\ \lim_{k\to 0^-} \frac{x}{k} &= \lim_{l\to -\infty} l \tag{$0^-$}\\ \mathcal{F}(x) &= \int_{-\infty}^{\infty} f(x)\ e^{-2\pi i x}\,dx\tag{FT}\\ \mathcal{F^{-1}}(x) &= \int_{-\infty}^{\infty} f(x)\ e^{2\pi i x}\,dx\tag{IFT}\\ \int_{-\infty}^{\infty} f(x)\,dx &= \lim_{h \to 0} \sum{\frac{f(x)+f(x-h)}{2}} \tag{sum limit integral}\\ \end{align}

So the fourier transform (and the inverse fourier transform) are defined in terms of integrals, which are themselves defined in terms of limits.

Limits distribute over summation, so it seems to me that it would be possible to simply use IEEE 754 floating-point numbers (which follow the limit-rules for division by zero) to find a correct answer, which would allow for a very fast computer-implementation of a deconvolution algorithm.

As an aside, I wonder if the fact that $h[n]$ is a FIR-filter (and linear, time-invariant and causal) is useful in some way.

Is my reasoning correct, or is it flawed somewhere?

Answer 1

Integral definition

So the fourier transform (and the inverse fourier transform) are defined in terms of integrals, which are themselves defined in terms of limits.

Nope, the integrals are not just the limits of sums here. That would be true for Riemann integrals over smooth functions (try doing that difference quotient at a place where $f$ isn't continuous). It's not how the Lebesgue integral that we need to use when defining the Fourier transformation is defined.

And, especially, if you understand the DFT as a "special use case" of the continuous FT, then you have to assume periodic repetition of the signal vector you're observing. Periodicity leads to line spectra. These are, by definition, not continuous.

So, no, your last equation isn't right.

Fourier Transform definitions

Your equations $(\text{FT})$ and $(\text{IFT})$ aren't how we write "The Fourier transformation of $f(x)$ is ...": Your left side of the equation doesn't say you're transforming $f(x)$; it doesn't mention $f$ at all!

One common way I see the "Fourier transform of $f$" (which is a function of the frequency $\omega$) being written is

\begin{align} \mathcal{F}\{f\}(\omega) \end{align}

and while we're at it, the right side of these equations is wrong, too: you're missing the $\omega$ (or whatever target-domain free variable you want to use) in the exponent.

Limit $l$

Now, the first two equations:

\begin{align} \lim_{k\to 0^+} \frac{x}{k} &= \lim_{l\to \infty} l \tag{$0^+$}\\ \lim_{k\to 0^-} \frac{x}{k} &= \lim_{l\to -\infty} l \tag{$0^-$} \end{align}

stand a bit on their own here, because you don't explain what $l$ is meant to be, but:

The right hand side of $(\text{$0^+$})$ and $(\text{$0^-$})$ don't exist. I mean, you literally write "when we not fix $l$ to any actual value, but let it simple pine for infinity, what's the actual value?". So, that actual value then doesn't exist.

Finding a substitute value of a function in a singularity

Is my reasoning correct, or is it flawed somewhere?

Yeah, at least the way it's written down, it's mathematically flawed.

Of course, you're right from a functional analysis point of view, your quotient function simply has a couple of singularities. That's not a problem per se!

Some of these singularities can actually be solved by finding a series on the environment of that point that is equal to the quotient in all but that point, and converges, and then "fix" the value at that point. However, that puts a huge restriction on your quotient function: It needs to be holomorphic in the neighborhood of that singularity for that series to exist. Sadly, quotients of holomorphic functions are only holomorphic where the denominator isn't zero. So, bad luck going the limit route!

What you're looking for is the residue theorem! I'll really quickly outline the idea:

• your quotient function is generally holomorphic, aside from a discrete set of points (where your denominator is 0 or your numerator goes towards infinity).
• If a function is holomorphic, than it has the (funky) property that if you have a "disk" (a non-intertwining surface with a closed boundary) on which it is defined, then you can fully infer the function from the values on the boundary of that disk. You might have met that, if you're an EE, used in Stoke's theorem (in electrodynamics)
• So, you just define a small disk around your singularities with radius $\gamma$, and let that radius get smaller. That should define how your quotient should behave in the singularity.

Problems

The above thing is a very analytical way of describing a system. Yes, if you have an analytic description of your quotient (hint: you do, see what sampling does and how we mathematically define the DFT as finite sum over holomorphic functions), you can apply that knowledge.

The practical problem arises from the fact that your quotient is based on an observation. Observations are noisy. Where an observed quality is close to 0, the noise component becomes dominant. If you divide by that, you get a huge amplification of noise!

So, whilst nice analytically, that's not the way you want to go in the real world. That's why all the deconvolution algorithms (there's actually quite a few) apply assumptions on the system being convolved with, and minimize some error term or maximize some likelihood term.