Polynomial Interpolation: Practice Versus Theory

I have posted several times, that it is possible to pre-compute a matrix, such that to multiply a set of input-samples by this matrix, will result in the coefficients of a polynomial, and that next, a fractional position within the center-most interval of this polynomial can be computed – as a polynomial – to arrive at a smoothing function. There is a difference between how I represented this subject, and how it would be implemented.

I assumed non-negative values for the Time parameter, from 0 to 3 inclusively, such that the interval from 1 … 2 can be smoothed. This might work well for degrees up to 3, i.e. for orders up to 4. But in order to compute the matrices accurately, even using computers, when the degree of the polynomial is anything greater than 3, it makes sense to assume x-coordinates from -1 … +2 , or from -3 … +3 . Because, we can instruct a computer to divide by 3 to the 6th power more easily than by 6 to the 6th power.

And then in general, the evaluation of the polynomial will take place over the interval 0 … +1 .

The results can easily be shifted anywhere along the x-axis, as long as we only do the interpolation closest to the center. But the computation of the inverse matrix cannot.

My Example

Also, if it was our goal to illustrate the system to a reader who is not used to Math, then the hardest fact to prove, would be that the matrix of terms has a non-zero determinant, and is therefore invertible, when some of the terms are negative, as it was before.

In this earlier posting, I wrote that if it was not our goal to determine a polynomial, which would require that a fractional value of X be put through that polynomial, but only our goal to interpolate a value of Y, corresponding to one known value of X, then the methods given suggest that a dot-product is possible, between several samples of Y, with a constant vector.

Well if the degree of the polynomial to use was 6, so that the order of the approximation was 7, then also, for a value of X equal to 0.5 , the vector of input-samples would need to be multiplied by this. I have stuck to¬† my convention of naming this midpoint ’15’, even though it might be more-aptly named ’05’ in this case, since it occurs at 0.5 . Please beware that this midpoint would have 4 samples preceding it, but only 3 following it, thus accounting for the lack of symmetry.

does not understand row vectors. The concept is to post-multiply the polynomial matrix I had generated before, by one row vector that represents the powers of the fractional value of X, thus obtaining one row vector, which is easy to write in pure Math. But to compensate for what cannot do, I needed to transpose the polynomial matrix first, and then to pre-multiply it by the corresponding column vector.

In the earlier exercise, I had failed at my goal to predict the cosine-wave at 0.75 Nyquist Frequency, more closely than the aliased frequency, which would have been 1.25 Nyquist, and more closely so than a linear interpolation would have accomplished.

This is to be expected, since that exercise only took into account 4 samples. What was perhaps not expected, was that the exercise can in fact be expanded to a 6th-degree polynomial. And so the following graph shows that because up to 7 samples can be taken into account, midway between X = 0 and X = 1 , this higher polynomial hugs the intended frequency very well, and ignores the aliased frequency completely:

poly-6th-deg_1

This was the wxMaxima worksheet, which produced that plot.


 

This is what would happen at 18kHz:

poly-6th-deg_3


 

(Edit 03/20/2017 : )

After some thought, I have come to the conclusion that a polynomial of the 6th degree, forming a 7th-order approximation, should not only be high-quality enough for 2x oversampling, but should actually be high-quality enough for 4x oversampling. This can be stated in a 7×3 matrix.

If 4x oversampling was used again in digital audio, the advantage would be that instead of chaining 3 Sallen-Key Butterworth Filters, and only being able to suppress the higher Nyquist Frequency by 50db or so, it should be possible to take advantage of having two octaves of separation, and to suppress the Nyquist Frequency by 72 db.

However, it would seem that this approach is only useful for playback, not for capture.

Dirk

 

Print Friendly, PDF & Email

Leave a Reply

Your email address will not be published. Required fields are marked *

Please Prove You Are Not A Robot *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>