# Question:

Extensively searching the space of all possible vectors of length $$n$$ to satisfy a (non-overdetermined) requirement is possible in principle. Hence, there is a way to calculate a complex FIR kernel of length $$n$$ whose magnitude response goes through $$2n$$ given points, when its phase response is allowed to be completely arbitrary. (Corollary, a real FIR kernel with $$n$$ given magnitude points and $$n$$ mirrored points can be calculated.) The extensive search method is hopelessly inefficient, though. Is there a practical way to calculate an FIR with such requirements?

# Context:

It is common DSP practice to use the DFT to convert an array of real magnitude points $$M = \{m_0, m_1, \dots, m_{n-2}, m_{n-1}\}$$, $$m_i \in \mathbb{R}$$ along with an array of real phase points $$P = \{p_0, p_1, \dots, p_{n-2}, p_{n-1}\}$$, $$p_i \in \mathbb{R}$$ to an FIR kernel $$K = \{k_0, k_1, \dots, k_{n-2}, k_{n-1}\}$$. $$K$$'s elements are generally complex, but if $$M$$ is symmetric (i.e. $$m_i = m_{n-i}$$ for $$0 < i < \frac{n}{2}$$) and $$P$$ is conjugate symmetric (i.e. $$p_i = - p_{n-i}$$ for $$0 < i < \frac{n}{2}$$), then $$P$$'s elements are completely real.

The magnitude response (absolute value of the DFT) of $$K$$ will always match $$M$$ at the individual points $$m_i$$. Between these fixed points, however, it can attain very unintuitive and undesirable values. This undesirable behavior can easily be visualized by appending a large number of zeros to $$K$$ and then calculating the absolute value of the DFT. Changing any $$p_i$$ changes the behavior of the magnitude response of $$K$$ in between the $$m_i$$. Thus, two FIRs derived from the same magnitude spectrum $$M$$, but with different phase spectra $$P$$, can have very dissimilar magnitude responses. This is illustrated by the figure below:

The upper plot shows three randomly chosen examples of $$P$$, called $$P_0$$, $$P_1$$ and $$P_2$$. The lower plot shows a randomly chosen example of $$M$$ and the resulting magnitude responses when an FIR kernel is formed using $$M$$ as the magnitude spectrum and one of the $$P_i$$ as the corresponding phase spectrum. $$n$$ was chosen to be $$16$$ here. The three magnitude responses all go through the fixed set of points defined by $$M$$, but vary considerably everywhere else, due to their different phase spectra.

There are many audio applications where we do not really care about the phase response of a filter, but we absolutely do care about the magnitude response. Given a magnitude spectrum $$M$$, we can hence regard all the $$p_i$$ as degrees of freedom to shape our magnitude response. More specifically, this should allow us to define $$n$$ additional magnitude points that the magnitude response of $$K$$ is required to go through. These additional requirements should be able to help to substantially reduce any undesirable magnitude response behavior of $$K$$ without the need to increase its length $$n$$. Calculating $$P$$ to satisfy such additional requirements seems nontrivial, though.

Are my assumptions correct? Am I missing something? Is there any practical (polynomial complexity) way to do this?

# Edit:

This seems to come down to the question of wether a complex polynomial can feasibly be interpolated by a number of absolute value requirements. The coefficients of the FIR kernel $$K$$ define a polynomial in the complex plane and $$K$$'s frequency response lies on the unit circle. Any magnitude requirements are positions on the unit circle with a value which the absolute value of that polynomial is supposed to go trough. Consequently, I asked a more specific question on Mathematics Stack Exchange. If I gain any further insight from there, I will update or answer my own question here.

• For future reference, there is a corresponding discussion on dsprelated.com. – Lasse Dec 22 '18 at 16:33

There are a few things that can make this easier

1. If you don't care about the phase response you can typically get the best result with calculating a minimum phase for your amplitude spectrum and using that as the complex target
2. If you want to control the in-between and the behavior at the band edges you need to specify targets points there as well.
3. If you have more target points then FIR coefficients, you have an over determined system but you can still solve it with a least square error approach. this will not hit all your target points exactly but it's often a good compromise between filter fidelity and computational complexity.
4. A least square error approach has the added advantage that you can apply weights to steer the solution towards a trade off that fits your requirements. For example, you typically need to control the out of band behavior: you don't care about the exact behavior other than it shouldn't have too much gain. To achieve this, you can set the target simply to zero and play around with the weight until the gain in that band feels acceptable
• Thanks for your answer. Just to be sure (regarding 3.): If I have n FIR coefficients and specify 2n target points, but these target points only define magnitude, not phase, then the system isn't overdetermined, right? Because each complex FIR coefficient "counts as" 2 degrees of freedom. Or am I missing something? – Lasse Dec 7 '18 at 17:54
• @Lasse. Depends on how you set up the systems of equations. If you use the complex amplitude as the target, you get a system of linear equations. In this case the least square solution is straight forward and fairly easy. If you use magnitude (or, better, magnitude squared), you end up with a nasty set of non-linear equations that's a lot harder to solve. Setting the phase to zero and still doing the linear equations doesn't help, since the linear coefficients are still complex. You still need 2n FIR taps to meet n target points. – Hilmar Dec 9 '18 at 3:06
• I guess my question is whether there is a feasible way of solving such a nasty non-linear equation system when using magnitude or magnitude squared. I have posted two follow-up questions on cs.stackexchange (cs.stackexchange.com/questions/101211/…) and math.stackexchange (math.stackexchange.com/questions/3032046/…) to address this. I will edit or answer my own question here if I get any answers. – Lasse Dec 9 '18 at 5:35
• @Lasse: not that I know of. In the filters I worked with (mostly audio), trying to hit a few target points exactly resulted in filters that were very poorly behaved at the non-target frequencies. I found over specifying and using least squares much more effective. I also found that minimum phase works quite well as a starting point, if you only interested in the magnitude. I have an idea for an iterative algorithm to solve for magnitude only, but never had a chance to to try it. Finally, your numerically stability depends a lot on the frequency grid: linear is good, log is tricky – Hilmar Dec 10 '18 at 12:02
• Thanks. I too find minimum phase to work quite well most of the time, but not always. Since one theoretically has the freedom of adjusting the phase to obtain other frequency responses between the targeted points, I was curious if this would be applicable in practice. I will experiment some more with least squares. I would be interested in your algorithm in case you would be willing to share your idea. – Lasse Dec 11 '18 at 12:38

This is only a partial answer: There is not generally an FIR kernel of length $$n$$ whose magnitude response goes through $$2n$$ given points, as explained by this follow-up post.

When only $$n$$ points are given, the magnitude response between these points can still be altered by adjusting the phase (angle) at any of these $$n$$ points. It is possible to satisfy some additional requirements this way in some special cases, but, as stated above, it is not always possible.