Is convolution the only way to apply filters?

Question

I've read about the discrete convolution and how it applies to filters, but is convolution the only way to apply filters (to input signals)?

The answer is "kind of". Covolution in the time domain leads to FIR and IIR filters. There also is the multiplication in the frequency domain, but that equals convolution in the time domain: $$ x(t)*y(t) => X(f)\cdot Y(F) $$
In the end, everything can be traced back to one form of convolution or another. — Jan Krüger, Jul 02 '16 at 09:44
@JanKrüger Is then for example the direct evaluation of direct forms also convolution? Such as what Matlab's filter() claims to do. — mavavilj, Jul 02 '16 at 09:46
@mavavilj what else should it be? Have you read the mathematical expression that filter computes? It's a discrete convolution! — Marcus Müller, Jul 02 '16 at 10:10
@mavavilj Yes, it is. Convolution is nothing else than a mathematical operation, constructed from an integral (which, in essence, is a sum), one signal (the filter kernel for example) turned around ($0..k => k..0$) and a multiplication. This is also what Matlabs filter() does. This is also what hardware filters do, no matter how they are arranges (one MAC cycling over the whole signal, FIR/IIR transversal, etc). — Jan Krüger, Jul 02 '16 at 11:03
by the way, we're only considering digital, linear filters, right? because there are other types of filters, but they are kind of rarely used, and especially Matlab's filter has nothing to do with them. — Marcus Müller, Jul 02 '16 at 11:04
By the way, your question sounds a lot like the good old X/Y problem . Maybe you want to open another question, explaining why you're wondering whether filtering is convolution. — Marcus Müller, Jul 02 '16 at 11:05
@MarcusMüller No, I'm trying to ask whether convolution is all that's needed to know for "applying filters" or whether there are other application methods. — mavavilj, Jul 02 '16 at 12:36
Well, it's not the only way of "applying" a filter, but all other methods than convolution are 100% mathematically equivalent to convolution. So, I guess your question is answered? I have another question for you then: Why are you asking this? — Marcus Müller, Jul 02 '16 at 12:56
@MarcusMüller Because I wanted to be sure that my intuition about convolution being the only one was right. — mavavilj, Jul 02 '16 at 13:03
Just to add a bit of precision: the use of convolution to calculate a system's output is valid only when the system is LTI. — MBaz, Jul 02 '16 at 14:38

Matt L. · Accepted Answer · 2016-07-02T16:35:48.893

5

For this discussion it's important to restrict the class of filters to linear time-invariant (LTI) filters. Their input-output relation is described by the standard convolution sum (or, in continuous-time, convolution integral) that you've probably come across. So the operation of any LTI system can be described by a convolution. In discrete time you have

$$y[n]=\sum_{k=-\infty}^{\infty}h[k]x[n-k]\tag{1}$$

where $x[n]$ is the input signal, $h[n]$ is the system's impulse response, and $y[n]$ is the output signal. An example where $(1)$ is implemented directly is the transversal filter, which has a finite impulse response (FIR).

However, this doesn't mean that an LTI system can only be implemented by directly implementing the convolution sum ($1$). Any infinite impulse response (IIR) must be implemented recursively, because the convolution sum $(1)$ can't be computed exactly in finite time (since it's an infinite sum). But mathematically, any recursive implementation of an IIR filter computes the same thing as the convolution sum.

The convolution sum can also be implemented in the frequency domain, where blocks of data are transformed using the DFT, these frequency domain data are modified according to the desired impulse response, and after applying an IDFT, the data blocks are combined to give the desired output signal. Two such methods are the overlap add and the overlap save methods.

In sum, all LTI systems are described by a convolution sum (or integral), but there are many ways to implement that sum, and more often than not, the convolution sum is not evaluated directly.

edited Jul 02 '16 at 16:35

answered Jul 02 '16 at 16:11

Matt L.

89,963
9
79
179

So is there something else than LTI systems, in digital filters? – mavavilj Jul 03 '16 at 10:16
@mavavilj: Sure, why not? – Matt L. Jul 03 '16 at 10:18
@mavavilj: E.g., adaptive filters, non-linear filters, etc. – Matt L. Jul 03 '16 at 10:22
So then the answer to my question should be "yes, but only for LTI systems"? – mavavilj Jul 03 '16 at 10:30
@mavavilj: Well, the problem is that your formulation "the only way to apply filters" is a bit unclear. Does "apply" mean implement? My answer should clarify all those details, please read it (again), and ask questions if necessary. Especially the last sentence of the answer should actually make things clear. – Matt L. Jul 03 '16 at 10:37
Apply means to apply the filter to the input signal. – mavavilj Jul 03 '16 at 10:38
@mavavilj: Sure, but do you mean in an actual implementation, or on paper? Again, my answer (hopefully) addresses and clarifies all those details. I don't understand what is still unclear to you. – Matt L. Jul 03 '16 at 10:39
Why would actual implementation differ from paper? – mavavilj Jul 03 '16 at 10:44
@mavavilj: Did you read my answer? E.g., it says "Any infinite impulse response (IIR) must be implemented recursively, because the convolution sum (1) can't be computed exactly in finite time". So on paper you can write down the convolution sum, but in practice you don't have the time to sum an infinite number of terms. – Matt L. Jul 03 '16 at 10:52
But what about discrete convolution. – mavavilj Jul 03 '16 at 10:55
@mavavilj: Eq (1) is discrete, otherwise it should be an integral. – Matt L. Jul 03 '16 at 11:06
Perhaps I meant finite convolution. – mavavilj Jul 03 '16 at 14:19
@mavavilj: If you have a discrete-time convolution with a finite length impulse response (FIR), then you can compute the convolution sum directly, but you don't need to (you can also do a frequency domain implementation. Again, all of this is in my answer (see the second paragraph from the bottom). – Matt L. Jul 03 '16 at 18:02

score 1 · Answer 2 · edited Apr 13 '17 at 12:47

What is a filter anyway? In every-day life:

a device that is used to remove something unwanted from a (generally) fluid substance

In computer programming?

a program or section of code that is designed to examine each input or output request for certain qualifying criteria

In data processing, we are somehow inbetween. The fluid substance (signal) should be removed from something unwanted not satisfying some qualifying criteria (noise).

Depending on the criteria, you have many choices, depending on assmptions. For instance median, min-max filtering, all depending on certain qualifying criteria.

If you trust in filtering that does not depend on the actual time, and that is linear (the sum of two filtered signals is the filtering of the sum of two signals), you get "linear time_invariant filtering" (LTI). Then, one quickly understands this is strongly related to Fourier basis and convolution. Many other sources can provide you with insights:

Then, you can apply linear filters the convolutive way. But thanks to the above Fourier relation, you can apply them in the Fourier domain, using recursive filters, with lattice formulations, etc. All of them ultimately yield linear filters, but the different implementations vary in efficiency, complexity, economy, robusness to errors, etc.

Is convolution the only way to apply filters?

2 Answers2