Why are recursives methods useful for FIR filter design?

Question

As I understand it, FIR filtering is a linear process. That mean for me that the whole filtering process will have a fully predictable behavior. So, could someone explain why a universal deterministic and optimal filter design method to obtain the desired response doesn't exist and why recursive approach seems to be of great interest in practice ?

EDIT: just to clarify, my question is about an "optimal" method, that is one which compute the shortest filter response while staying the closest to the design criteria.

Answer 1

Sure, FIR filters are "simple" linear objects. But a typical FIR filter design task looks like this:

Find a set of numbers (the filter coefficients) such that the magnitude of their Discrete Fourier Transform is as close as possible to a target response. "As close as possible" being defined as "by minimizing the $L_\infty$ norm of the difference between ideal and actual response over some frequency ranges".

This is a non-linear, sometimes non-convex optimization problem and there is no universal, trivial procedure to solve those.

We have to use procedures like the Parks-McClellan algorithm because the real-world engineering constraints we want to impose when designing FIR filters do not translate into simple linear or quadratic constraints. For example, a least-square error criterion (L2 norm often leads to more tractable procedures than other norms...) would not be an acceptable choice for engineering applications, because it could allow solutions that are close to the required response on average, but with an outlier value.

Answer 2

The question seems a bit vague - there are plenty of other situations where the system (or its model) is considered to be completely deterministic, but you have tradeoffs, or a complex 'quality metric' which makes good design a challenge.

One observation that may help: The frequency response of an FIR filter is continuous in all of its derivatives (since it can be written as a sum of continuous functions via fourier transform). So, if the filter's response is completely (mathematically) flat for any finite part (however small) of the spectrum, then it must be completely flat throughout the spectrum, and is therefore not very useful.

So, you clearly can't have an FIR filter with a perfect passband or stopband. You can get very close with a large enough filter, though. Designing the filter is a tradeoff amongst all the imperfect, feasible filters; balancing whatever design criteria you have (this applies equally to IIR filters).

Answer 3

IIR filters are also linear (and time-invariant). what that means is that the mapping from input samples $x[n]$ to output samples $y[n]$ satisfies the superposition (and time-shifting) properties:

if $$y[n] \triangleq \mbox{LTI} \{ x[n] \}$$

then $$y_1[n] + y_2[n] = \mbox{LTI} \{ x_1[n] + x_2[n] \}$$

and $$ y[n-D] = \mbox{LTI} \{ x[n-D] \} $$

and, as a result, the convolution summation:

$$y[n] = \mbox{LTI} \{ x[n] \} = \sum_{k=-\infty}^{+\infty} h[k] x[n-k]$$

for some impulse response $h[n]$ (which are the coefficients for the FIR) that is dependent only on the filter, not the input. that's what linear and time-invariant means.

but in both cases, FIR or IIR, the mapping of the specifications of the filter to those coefficients $h[n]$ is the "filter design" process. why would that be linear? there is no reason for that.

so, perhaps one method might be you make a guess at what the coefficients are, see what you get regarding the coefficients, and then somehow tweek or adjust your guess to be a better guess in the next recursion. now algorithms like the Parks-McClellan (based on the Remez exchange algorithm) are more complicated than "guess and tweek", but that is what they are doing.

you can get very good results with the "windowing method" (if you use a good window function, like the Kaiser) and that is not recursive.