14
$\begingroup$

What are the differences between classical low-pass filtering (with an IIR or FIR), and "smoothing" by localized Nth degree polynomial regression and/or interpolation (in the case of upsampling), specifically in the case where N is greater than 1 but less than the local number of points used in the regression fit.

$\endgroup$
  • $\begingroup$ +1 Great question, you beat me to it. :-) AFAIK using N=2 corresponds to the linear 'classical' filtering we are familiar with, but I could be wrong on this. $\endgroup$ – Spacey May 7 '12 at 16:41
  • 2
    $\begingroup$ sinc reconstruction vs spline interpolation: cnx.org/content/m11126/latest "the spline interpolation is smoother than the sinc interpolation. This is because the support of the cardinal splines is more compact than that of the sinc function." $\endgroup$ – endolith May 7 '12 at 19:43
10
$\begingroup$

Both low pass filtering and polynomial regression smoothing could be seen as approximations of a function. However, the means of doing this are different. The key question to ask here is "Can you do one in terms of the other?" and the short answer is "not always", for reasons that are explained below.

When smoothing by filtering the key operation is convolution where $y(n)=x(n)*h(n)$, which in the frequency domain translates to $y=F^{-1}(F(x)F(h))$ where $F$ denotes the Discrete Fourier Transform (and $F^{-1}$ the inverse). The Discrete Fourier Transform (e.g. $F(x)$) offers an approximation of $x$ as a sum of trigonometric functions. When $h$ is a low pass filter, a smaller number of low frequency components are retained and the abrupt changes in $x$ are smoothed out. This sets low-pass filtering in the context of function approximation by using trigonometric functions as the basis functions, but it is worth revisiting the convolution formula to note that when filtering, y(n) (the output of the filter) depends on $x(n)$ as well as a weighted sum of past samples of $x$ (the weighting here determined by the "shape" of $h$). (similar considerations hold for IIR filters of course with the addition of past values of $y(n)$ as well)

When smoothing by some n-degree polynomial though, the output of the interpolant depends only on $x(n)$ and a mixture of (different) basis functions (also called monomials). What are these different basis functions? It's a constant ($a_0x^0$), a line ($a_1x$), a parabola ($a_2x^2$) and so on (please refer to this for a nice illustration). Usually though, when dealing with equi-distant samples in time and for reasons to do with accuracy, what is used is Newton's form of the polynomial. The reason i am citing this is because through that it is easy to see that when performing linear interpolation you could construct a filter kernel that returns a linearly weighted sum of available samples, just as a low order interpolation polynomial would use "lines" to interpolate between two samples. But at higher degrees, the two approximation methods would return different results (due to the differences in the basis functions).

As i wrote above, not taking into account past values of $x(n)$ is not strict. This is a subtle point. Because usually, when building a polynomial the values outside the given interval ("past" and "future" of a signal) are not considered. It is however possible to include these by fixing the derivatives at the edges of the interval. And if this is done repeatedly (like a non-overlapping sliding window) then effectively, the "past samples" of x(n) would be taken into account. (This is the trick that splines use and in-fact there is a convolution expression for bicubic interpolation. However, please note here that the interpretation of $x$ is different when talking about splines -note the point about normalisation-)

The reason for using filtering as interpolation some times, say for instance in the case of "Sinc Interpolation", is because it also makes sense from a physical point of view. The idealised representation of a band-limited system (e.g. a (linear) amplifier or lens in an optical system) in time domain is the sinc pulse. The frequency domain representation of a sinc pulse is a rectangle "pulse". Therefore, with very few assumptions we expect a missing value to be more or less near its neighbours (of course, within limits). If this was performed with some n-order polynomial (for higher n) then in a way we "fix" the way that a missing value is related to its neighbours which might not always be realistic (why should the sound-pressure values of a wave-front hitting a microphone be fixed to have the shape of a $x^3$ for example? It puts an assumption on how the sound-source behaves which might not always be true. Please note that i do not imply any suitability of an interpolation scheme from a psychophysics point of view here, which involves the processing of the brain (see Lanczos resampling for example). I am strictly speaking about constraints imposed by interpolation when one tries to "guess" objectively missing values.

There is no universal "best method", it pretty much depends on the interpolation problem you are faced with.

I hope this helps.

P.S. (The artifacts generated by each of the two approximation methods are different as well, see for example the Gibbs Phenomenon and overfitting, although overfitting is "at the other side" of your question.)

$\endgroup$
  • $\begingroup$ +1 Excellent answer. Some follow ups: 1) You mention not taking into account past values of x[n] in polynomial fitting, however, isnt this a moot point based on what you have said about x[n] being a a summation of sines/cosines anyway? (Past values taken into account or not, this still holds). 2) I am somewhat confused by the physical interpretation of something being 'band-limited' in this case. Isnt everything band-limited? That is, will pass certain frequencies and and attenuate others? What is a physical example of a non-bandlimited system? Thanks. $\endgroup$ – Spacey May 8 '12 at 15:40
  • $\begingroup$ 1) Not sure that i understand completely what you mean but i was referring to the differences between obtaining the output from convolution and from polynomial fitting. 2) In some cases, signals and systems are treated under the same framework. Theoretically there are signals that are not band-limited (en.wikipedia.org/wiki/…) such as (truly) white noise (en.wikipedia.org/wiki/White_noise). A very good treatment is available in Signals & Systems by Oppenheim and Willsky. I used the term here to make the connection between bandlimit->sinc $\endgroup$ – A_A May 8 '12 at 16:51
  • $\begingroup$ Ok, I have re-written my question - just to make sure: 1) The more higher order polynomial we use, the more 'biased' we are in forcing relationships between points, which might not fit the physical reality, yes? (More is not always better in this case.) 2) Regarding the band-limiting - I am just curious as to why we say this, because isnt EVERY system band limited, in that, it only takes in certain frequencies and attenuates others? Thanks. $\endgroup$ – Spacey May 9 '12 at 16:13
  • $\begingroup$ I am sorry this escaped my attention. For these specific questions: 1) Not neccessarily. In the example given i was referring to restrictions imposed by the "shape" of the monomials. 2) Signals & Systems will help a lot. Certain things are said to be exact as engineering applications use a subset of mathematics which in another field might have a very good use for non-band limited signals (like the truly uniform random process (white noise) linked to above). $\endgroup$ – A_A May 9 '12 at 22:07
2
$\begingroup$

Nice question and enlightening answers. I wanted to share few insights as follows. There exist orthogonal polynomial bases also such as Legendre's polynomial bases (in contrast to monomial bases) which are more stable in fitting higher degree polynomials. As sinc bases used in Shannon's interpolation formula (which indeed can also be seen as a convolution operation and hence a filtering operation) are orthogonal bases for a bandlimited Hilbert space, orthogonal polynomial bases may serve to approximate a larger class of functions not in the bandlimited space together with having the power of orthogonality with them.

Polynomial filtering (not interpolation) has also been there in Chemistry literature since 1960. A good lecture note on revisiting this topic has been written by R.Schafer titled, What is Savitzky-Golay Filter , link: http://www-inst.eecs.berkeley.edu/~ee123/fa12/docs/SGFilter.pdf

$\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.