3
$\begingroup$

Before I ask the question: I am from mechanical background and would appreciate a detailed answer.

Generally, for automobiles, I am trying to understand the following:

Given, say $1\;\mathrm{sec}$ of measurement data, which may contain a wide range of frequencies, we fit an $n^{\mathrm{th}}$ order polynomial curve through it. Doing this filters out certain frequencies which would have been present otherwise. It acts, as I can imagine, like a low pass filter.

Question:

Let us say that we have a linear system with input $u$. Let $f$ be the input frequency. This linear system would produce an output, $y$, of same frequency, $f$. We fit an $n^{\mathrm{th}}$ order polynomial through these measurements. This curve-fitting acts as a low pass filter. What would be the characteristics of this low pass filter?

Context to my question and discussion:

How I see it is: The measurement data is $1\;\mathrm{s}$. Fitting a parabola through it can be approximated as a half of a sinusoidal curve. Similarly, a $3^{\mathrm{rd}}$ order curve would be a complete sinusoidal curve, and so on. So, for $2^{\mathrm{nd}}$ order polynomial, the cut-off frequency $f_c$ would be $0.5 \;\mathrm{Hz}$. Similarly, $1 \;\mathrm{Hz}$ for $3^{\mathrm{rd}}$ order polynomial and so on. Does this make any sense? Could somebody suggest me some book where this aspect is dealt with?

$\endgroup$
  • $\begingroup$ Welcome to SP.SE! This is an interesting question... the problem is that as soon as the order of the polynomial starts getting large (bigger than 5?), solutions to such approximation problems get numerically unstable (without careful choice of the polynomials). $\endgroup$ – Peter K. Sep 20 '16 at 12:15
  • $\begingroup$ I appreciate the comment. It is indeed interesting. I am designing a controller for vehicle following and for me it is possible to filter unwanted behavior of the vehicle to be followed by just filtering the path that I get from measurements. I would like to be able to give exact mathematical description to this filtering effect in frequency domain. The initial understanding that I wrote down is too vague for me now to be put in mathematical terms...any reference would be appreciated. $\endgroup$ – Zero Sep 20 '16 at 12:32
  • $\begingroup$ SE.DSP wishes you a happy new year 2017, with a kind reminding signal that your question or its answers may require some action (update, votes, acceptance, etc.) $\endgroup$ – Laurent Duval Jan 2 '17 at 22:55
3
$\begingroup$

Generally speaking, I would not call a polynomial, in general, a low-pass approximation to a signal. Per se, talking practically, standard definitions of the Fourier transform do not allow polynomials on $]-\infty,\infty[$ to have a useful spectrum. Generally speaking, polynomials (except constants) tend to infinity at fast rate, hence cannot be really limited in frequencies.

So it is difficult to say a polynomial filters out certain frequencies. However, locally, on an interval, they can pass nicely through data points, so they can smooth data, to some extend. Typical examples are sensor trends or drifts, when they are monotonous, and peaks or bumps.

You can find a lot of works on polynomial trend filtering, or polynomial peak filters. When the cost function for those fits is a squared error, you end up with a linear system in the polynomial coefficients, which turns into a weighted average of signal samples, that can be interpreted as coefficients of a linear filter. A famous example is the Savitsky-Golay filter, which was recently analyzed in frequency in 2011 by R. Shafer: What Is a Savitzky-Golay Filter?. This family of filters is also interesting as they provide smoothed derivatives.

But you can also fit a polynomial with other loss functions, like the $\ell_1$-norm, or with additional penalties. They are currently active topic in signal processing (I am working on some extension to Savitsky-Golay filters). Here are a few references, to start from:

$\endgroup$
  • $\begingroup$ I really appreciate the suggestion and commend you for that. I would still require some time to go through this list. I would like to leave this question open for some more time to attract some more answers. Once I go through the stuff I may have some more questions for you :) $\endgroup$ – Zero Sep 23 '16 at 12:12
1
$\begingroup$

Given, say $1sec$ of measurement data, which may contain a wide range of frequencies, we fit an $n^{th}$ order polynomial curve through it. Doing this filters out certain frequencies which would have been present otherwise. It, as I can imagine, acts like a low pass filter.

Yes. And, No.

I suppose that you are referring to very, very, very low order (with respect to the length of the dataset) polynomials. Due to the way polynomial fitting works, you quickly find yourself dealing with very small or very large numbers and numerical instabilities creep in. One second of data at 44.1KHz is 44100 data points. Fitting a 1024 order polynomial covers only about 2% of the original data points and would still require to raise numbers in the range $0 \ldots 1$ to the power of 1024.

Furthermore, please note that while you are shifting to the next window of interpolation (a new second of data comes in) you will have to now take into account constraints. That is, the beginning of the interpolation is not free to move anywhere it likes now. The curve must start as the last one ended to ensure continuity...Otherwise you get "clicks" as the waveform jumps at the transition. In fact, as far as polynomial fitting is concerned, you will most certainly get clicks because the curve will depart at whatever slope least squares dictates, in order to minimise the error and there, since you cannot know the future, it is very difficult to enforce constraints (that is, "no matter what, I want the curve to finish at a straight line segment with specific slope").

Fitting a parabola through it can be approximated as a half of a sinusoidal curve

No.

Where is the rest of the sinusoid and what will you do with a parabola "in between"? That is, as the peak slides off the window and we now enter the trough. A parabola could fit part of a sinusoid but it cannot substitute it.

This curve-fitting acts as a low pass filter. What would be the characteristics of this low pass filter?

To ask this, is to ask, how can I express one in terms of the other? That is, can I find an equivalence between polynomial fitting and low pass filtering as a reduced sum of trigonometric functions? And the answer is no because of the vastly different way that these two are structured.

Another thing to consider is the way that least square works, because, least squares will just strive to fit a parabola to the data even if it is not there. Well, what if my $n,x(n)$ doesn't bend it like a parabola? In fact, if your signal does not contain a component that varies with some combination of polynomial functions, the fit will fail. A prime example of this are impulsive functions. Take a beat that contains a bass drum (low frequencies) and a high hat (high frequencies) and try to "cut" the high hat using polynomial fitting. It's impossible. Polynomial fitting will try to make sense of everything, including the silence between the beats. The polynomial MUST fit. Least squares MUST find a local minimum.

An exception here might appear to be piecewise spline interpolation that split the waveform into parts and fit smaller polynomials, with constraints, between them but again, their definition doesn't allow for an easy transition between their spline representation and the Fourier Transform via which you could then "jump" to an impulse response. That is, to say that given the coefficients of a fitted piecewise spline, you can find a way to derive the impulse response of a Finite Impulse Response filter (let alone an Infinite Impulse Response filter).

You can always try to obtain a large sample of your data, fit a smoothing spline and then obtain the Fourier Transform of that to see what sort of low pass filter could approximate the result of the spline but that's not a way of deriving equivalent filters.

Hope this helps.

$\endgroup$
  • $\begingroup$ I appreciate the comment...I'll go through the answers you have posted on a similar question and get back to you later $\endgroup$ – Zero Sep 23 '16 at 12:14
  • $\begingroup$ No worries. In the meantime, feel free to include more context to your questions in the future. Even if this means talking about mechanics at a level that you think might be too specialised. Anything more that you add to the problem helps a lot with the answer (for example, see what the original Q/A was here and how it changed after more information was revealed). Finally, by what you are describing it is likely that a Kalman filter might be of more help to what you are trying to do. $\endgroup$ – A_A Sep 23 '16 at 13:16
0
$\begingroup$

This method seems a bit unusual to me.

To me, curve-fitting is not equivalent to a low-pass filter. By definition, a well-constructed low-pass filter suppresses high-frequency components of a signal and allows low-frequency components to pass through (relatively) unchanged. The output of a polynomial fit doesn't do that. Depending on the order of the polynomial, it does indeed suppress the high-frequency components, but it will (in some cases, significantly) change the low-frequency components as well. So while you would, for example, Fourier transform the output of a low-pass filter, you wouldn't do that on the output of a polynomial fit.

Polynomial fits are usually done when you don't actually care about the relative amplitudes of the various frequency components, but instead are looking for an overall shape. So you would use them for interpolation, for example, or to match a pre-defined model. But I don't think I would use them like I would use a filter.

$\endgroup$
  • $\begingroup$ I agree in part and diagree in part...While a curve fitting procedure is not a perfect low pass, it does have its chracteristics. While polynomial fitting is used to "smoothen" out the curve to reduce noise, its design can tell you which frequencies it cannot follow. e.g. the vehicle in front is moving at a freuency say 2 Hz (imagine it like a snake on the road.) Now if I take 1 sec data and fit a parabola through it, I cannot see that 2 Hz movement or even 1 Hz for that matter. So while not a low pass, it definitely has the characteristics $\endgroup$ – Zero Sep 21 '16 at 6:57
0
$\begingroup$

This is an interesting perspective.

When you say you want to fit an nth order polynomial through your "system", I assume you are talking about the impulse response. So you're modelling your impulse response in time with polynomials.

Shouldn't you just find the spectrum of the polynomial transfer function? Wouldn't that give you the exact spectrum of the model? As you decrease the degrees of freedom in your polynomial model, you are going to have higher and higher order terms added to your model. This means you will just have to account for higher order polynomials in your fourier transform. What am I missing here?

$\endgroup$
  • $\begingroup$ What do you mean by polynomial transfer function? $\endgroup$ – Zero Sep 21 '16 at 7:06
  • $\begingroup$ What exactly are you modelling with polynomials? Is it the frequency response of your system, or the time domain impulse response? $\endgroup$ – Tom Mathew Sep 21 '16 at 17:09
  • $\begingroup$ The data I have is the physical displacement of a point at the rear bumper of a vehicle in front of me. The displacement is in sideways direction. So vehicle steers at a frequency, and the resulting motion has the same frequency which I see in my measurements. I fit a curve and generate a vehicle yaw rate required to track the path. Then I finally covert yaw rate to my vehicle steer input. If done right, I copy yaw rate. Hence copy steer input. Since it is not perfect, I copy accurately up to a frequency which curve fits. That would be frequency I follow $\endgroup$ – Zero Sep 22 '16 at 0:38

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.