5
$\begingroup$

I have an input time series going through a filter that creates another time series as output.

If I assume in first approximation that my filter is linear, does it necessarily mean that I can model this filter by a convolution?

In other words is it only certain types of linear filters that can be modelled by a convolution? (LT1?...).

I have never seen any clear statement on this in any publication. It is as obscure and vague as definitions of time invariance, ergodicity, causality etc in filtering textbooks.

My question comes from wondering if there is any point trying to attempt an already risky deconvolution if I am not even sure that my linear filter is necessarily akin to a convolution.

Why classes of linear filters are not clearly explained in publications (that I know of) is a mystery to me, as it should perhaps be the first question that arises when trying to model real world phenomenons.

$\endgroup$
6
$\begingroup$

No. It's only LTI (Linear and Time-Invariant) systems that can be modeled with convolution through a unique single impulse response.

For example the systems

$$ y(t) = g(t) x(t) $$ or $$ y[n] = \sum_{k=0}^{k < n} x[n-k] $$

are both linear but not time-invariant and their output $y[n]$ cannot be computed with the convolution operation ( $\star$ denoting convolution)

$$ y[n] = x[n] \star h[n]$$

as such an impulse response $h[n]$ does not exist.

$\endgroup$
  • $\begingroup$ Thanks indeed. I work in earth sciences and following your answer I will check now why we throw comvolutions in so easily in seismic modelling. $\endgroup$ – Poseidon Oct 12 at 10:49
  • $\begingroup$ @Fat32: If I'm wrong, you can just say NO ( since it means I'm lost ) but isn't your second example a moving sum ? If so, can it not be modelled using an impulse response approach where you use a moving window of one's for h(n) ? Thanks. $\endgroup$ – mark leeds Oct 12 at 15:35
  • $\begingroup$ @markleeds The upper limit depends on "n" and prevents it to be shift invariant. It's not a fixed length moving sum either. $\endgroup$ – Fat32 Oct 12 at 16:03
  • $\begingroup$ @Fat32: I wrote out some terms and realize what you are saying now. thanks. $\endgroup$ – mark leeds Oct 12 at 18:34
  • 1
    $\begingroup$ @Poseidon, I'd assume most models are linear and somewhat time invariant (i.e. the model is valid for a specific configuration that exists only during a finite time, but for any point within that time you can repeat the same experiment five minutes later and get the same results). If your model includes an energy source (e.g. a volcano or a plate boundary under stress), it is probably nonlinear, but simple propagation of pressure waves is LTI. $\endgroup$ – Simon Richter Oct 13 at 0:33
3
$\begingroup$

Any LTI system can be completely characterized (among other things) by it's transfer function or it's impulse response.

If your filter represents an LTI system, that you can calculate it's output by either convolving the input with the impulse response or multiplying the transfer function with the spectrum of the input signal.

In theory these things are equivalent, in practice they have their pros can cons.

A simple first order lowpass filter has an impulse response that's infinitely long. That makes convolution difficult since your convolution sum has an infinite number of terms. In this case it would be easiest to directly implement the difference equations and implement a standard IIR filter algorithm in the time domain.

$\endgroup$
2
$\begingroup$

The convolution integral is a special case of the Fredholm equation of the first kind.

https://en.wikipedia.org/wiki/Fredholm_integral_equation

I believe that it covers linear time varying systems, as do linear time varying state space equations, so it’s a no but... kind of answer.

$\endgroup$
  • 1
    $\begingroup$ That's interesting. I remember seeing that, but not under any particular name. $\endgroup$ – TimWescott Oct 12 at 20:37
1
$\begingroup$

To unveil part of the mystery, let us recall how the convolution operation and the properties of linearity and time-invariance are related. In other words, if a discrete system $\mathcal{S}$ is linear and time-invariant, what would be the output for a discrete signal $x[n]$?

To do that, let us rewrite the signal on the basis of Kronecker symbols $\delta_n$, which are zero everywhere, except at index $n$. Then:

$$ x(\cdot) = \sum_{n=-\infty}^{\infty} x[n] \delta_n$$

Since the system is linear, we know that, for each $n$, $\mathcal{S}(x[n] \delta_n) = x[n]\mathcal{S}( \delta_n)$. Thus, the system is fully defined by the outputs of all $ \delta_n$. Since the system is time-invariant, $\mathcal{S}( \delta_n)$ is just $\mathcal{S}( \delta_0)$, shifted by index $n$. So, the system $\mathcal{S}$ is fully understood if one knows its response to the unit discrete impulse $\delta_0$, the "aptly named" impulse response $h=\mathcal{S}( \delta_0)$. Hence,

$$\mathcal{S}\left( \sum_{n=-\infty}^{\infty} x[n] \delta_n \right) = \sum_{n=-\infty}^{\infty}x[n]\mathcal{S}\left( \delta_n \right) = \sum_{n=-\infty}^{\infty}x[n]h(\cdot - n)$$ which is the discrete convolution. Conversely, the convolution yields a linear and time-invariant system. Thus, LTI systems or filters are "almost" equivalent to "being modelled by a convolution" (provided that the series exist, for those picky on mathematical corrected). As precisely answered by @Fat32, as long as the filter is linear, but not time-invariant, it cannot be implemented via the classical convolution.

Honestly, most actual systems are not exactly time-invariant. However, one may expect that the time variance is slow, with respect to the signals they analyze. So deconvolution may work. And time-varying deconvolution is used. There are theories for generalized transfer functions, or time-variant/shift-variant filters, see for instance:

The paper considers filters described by linear shift-variant difference (LSV) equations. We present the notion of a generalized transfer function and discuss the frequency characteristic of a shift-variant digital filter in terms of the generalized transfer function. A method is presented for determining LSV difference equations from a certain class of impulse responses, and vice versa. In addition, some properties of the impulse response and the generalized transfer function of a shift-variant system are investigated in the present work.

A very important class of shift-variant systems (that are cyclic) are multi-input/multi-output (MIMO) filter banks.

$\endgroup$

Your Answer

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

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