Thread Subject: Polyval vs. Fourier analysis class question

Hello all,

I'm taking a class which uses MATLAB. Our instructor was using a set
of class notes to explain polyval and polyfit, and explained that the
final result may be a poor fit.

I asked why we emphasized polyval/polyfit instead of a Fourier type
of analysis. He didn't know (after all, he didn't write the book).
I suspect it's because dealing with polynomials is less CPU intensive
than dealing with sines and cosines, but I'm not sure.

Since I'm still new to Matlab, I am not sure where to go -
ultimately, the answer may be "That's just the way the text was
written." Still, I checked Cleve Moler's textbook, and it starts
explaining the topic the same way.

If this question makes sense, does anyone have an answer why the
topic is taught this way?

Thanks,
John

On Thu, 8 Jul 2004, John Guin wrote:

> Hello all,
>
> I'm taking a class which uses MATLAB. Our instructor was using a set
> of class notes to explain polyval and polyfit, and explained that the
> final result may be a poor fit.
>
> I asked why we emphasized polyval/polyfit instead of a Fourier type
> of analysis. He didn't know (after all, he didn't write the book).
> I suspect it's because dealing with polynomials is less CPU intensive
> than dealing with sines and cosines, but I'm not sure.

Both a polynomial fit and a Fourier expansion provide an orthogonal basis
set which can be used to approximate a function or a set of data.

Why would one basis be better than another? Computational efficiency,
convergence, etc all matter. One important consideration is that, except
in the special case of periodic data (or equivalently, data that can be
assumed to be periodic because you are only interested in a finite
region), one has a continuous Fourier spectrum - immediately a
computational difficulty.

If you can use a discrete Fourier transform, then FFT looks attractive
from considerations of efficiency, but requirements for 2^n equispaced
samples might be difficult to meet.

But, in principle, either can be used. What will be best will depend on
the particular case. Polynomial fitting might be preferred in your course
since it is often considered to be easier to understand.

As an educational exercise, try the same fitting with Fourier expansions,
see which is faster and better.

--
Timo Nieminen - Home page: http://www.physics.uq.edu.au/people/nieminen/
Shrine to Spirits: http://www.users.bigpond.com/timo_nieminen/spirits.html

Timo Nieminen wrote:

> Both a polynomial fit and a Fourier expansion provide an orthogonal
> basis
> set which can be used to approximate a function or a set of data.

I think technically normal polynomials {1,x,x^2,...} only provide a
linearly independent basis set,and only special polynomial sets are
orthogonal.

This means that you have to solve a linear system to get the
coefficients (coordinates)
of some function in terms of the basis set.

For an orthogonal set, the coordinates are independent, so can be
computed seperately.
e.g. for real numbers and vectors, you can compute the projection of
a vector onto the basis vectors (e.g. V_i = dot(V,i), V_j = dot(V,j),
etc.). I think for Fourier components it is similar.

Not something I'm too familiar with, but the orthogonal polynomials
are typically named after mathematicians, and are eigenfunctions of
certain PDEs (e.g. Chebyshev/Legendre polynomials?)

Matt

On Thu, 8 Jul 2004, Matthew Wolinsky wrote:

> Timo Nieminen wrote:
>
> > Both a polynomial fit and a Fourier expansion provide an orthogonal
> > basis
> > set which can be used to approximate a function or a set of data.
>
> I think technically normal polynomials {1,x,x^2,...} only provide a
> linearly independent basis set,and only special polynomial sets are
> orthogonal.

Yes, you are quite correct. IIRC, Gram-Schmidt orthogonalisation of
{1,x,x^2,...} gives the Legendre polynomials.

--
Timo Nieminen - Home page: http://www.physics.uq.edu.au/people/nieminen/
Shrine to Spirits: http://www.users.bigpond.com/timo_nieminen/spirits.html

John Guin wrote:
>
>
> Hello all,
>
> I'm taking a class which uses MATLAB. Our instructor was using a
> set
> of class notes to explain polyval and polyfit, and explained that
> the
> final result may be a poor fit.
>
> I asked why we emphasized polyval/polyfit instead of a Fourier type
> of analysis. He didn't know (after all, he didn't write the book).
>
> I suspect it's because dealing with polynomials is less CPU
> intensive
> than dealing with sines and cosines, but I'm not sure.
>
> Since I'm still new to Matlab, I am not sure where to go -
> ultimately, the answer may be "That's just the way the text was
> written." Still, I checked Cleve Moler's textbook, and it starts
> explaining the topic the same way.
>
> If this question makes sense, does anyone have an answer why the
> topic is taught this way?
>
> Thanks,
> John

I believe using polynomials comes from the idea that it is locally
possible to approximate a function by a polynomial (Taylor series).
Hence you try to do the same in a global way.

Fourier series are instead the natural thing to use if you try to
approximate periodic functions (or, equivalently, having fixed
boundary values).

Anyway, the naive thought is that the more terms the better
approximation you should get. And the lesson is: it does not work.
Neither with polynomials nor with trig series.

So you go to the next chapter which is probably about splines...

Cheers,
Jesper

"John Guin" <johnguin@hot_mail_.co.m> wrote in message
news:eee2781.-1@webx.raydaftYaTP...
> Hello all,
>
> I'm taking a class which uses MATLAB. Our instructor was using a set
> of class notes to explain polyval and polyfit, and explained that the
> final result may be a poor fit.
>
> I asked why we emphasized polyval/polyfit instead of a Fourier type
> of analysis. He didn't know (after all, he didn't write the book).
> I suspect it's because dealing with polynomials is less CPU intensive
> than dealing with sines and cosines, but I'm not sure.
>
> Since I'm still new to Matlab, I am not sure where to go -
> ultimately, the answer may be "That's just the way the text was
> written." Still, I checked Cleve Moler's textbook, and it starts
> explaining the topic the same way.
>
> If this question makes sense, does anyone have an answer why the
> topic is taught this way?

Dominant trends in data (especially time series like radar or optical
tracking sensors) tend to fall into two main classes:
a. polynomial (e.g., resulting from translational target motion)
b. periodic (e.g., resulting from rotational target motion)

Finer, more interesting details of the data may be obscured by the
dominant trends.

Therefore, a successful analysis may have to rely on removing
those trends. In general, both type have to be removed. This
can be done simultaneously or in stages. In the latter case
The trends are removed in order of dominance. Typically,
polynomial followed by periodic.

Consequently, both types of modeling should be in your bag of
tricks. Polynomial fitting is more basic and easier to understand,
so it is taught first, sometimes in high school. Fourier modeling
is much more difficult to master and, subsequently, is taught
later, usually in the upper classes in college.

When you were in grammar school, which made you more
comfortable:

1,x,x^2 or 1,cos(x),sin(x) ?

Hope this helps.

Greg

> I asked why we emphasized polyval/polyfit instead of a Fourier type
> of analysis. He didn't know (after all, he didn't write the book).

My reaction to this is that a typical fourier analysis of a data set
will fit n parameters (raleigh frequencies) to n data points. The
obvious consequence being that a naive fourier analysis is bound to
be compromised by some overfitting. Generally when people do
polynomial fitting they are very aware of these kinds of issues but
for some reason when they do fourier analysis they assume the FFT is
some kind of magic wand.

If you want to read a really good discussion of these issues try
D.J.Thompson Proc. IEEE Vol 70 no 9 pp1055-1096 or from a more
"applied" point of view P.P. Mitra and B. Pesaran. Biophysical
Journal Vol 76 feb 1999 pp691-708.

have fun!

"John Guin" <johnguin@hot_mail_.co.m> wrote in message
news:eee2781.-1@webx.raydaftYaTP...
> Hello all,
>
> I'm taking a class which uses MATLAB. Our instructor was using a set
> of class notes to explain polyval and polyfit, and explained that the
> final result may be a poor fit.
>
> I asked why we emphasized polyval/polyfit instead of a Fourier type
> of analysis. He didn't know (after all, he didn't write the book).
> I suspect it's because dealing with polynomials is less CPU intensive
> than dealing with sines and cosines, but I'm not sure.
>
> Since I'm still new to Matlab, I am not sure where to go -
> ultimately, the answer may be "That's just the way the text was
> written." Still, I checked Cleve Moler's textbook, and it starts
> explaining the topic the same way.
>
> If this question makes sense, does anyone have an answer why the
> topic is taught this way?
>
> Thanks,
> John

Curve fitting can be a good way to model data. The best approach will depend
on whether the selected model (e.g. polynomial vs. fourier vs. exponential,
etc.) is a good fit to the data, and what the model will be used for. Often,
you need to try several methods to find the one that works best for your
problem.
Fourier analysis is great for time-series data, especially when the data is
known to be band-limited. and just because you have N data points, doesn't
mean you need N Fourier coeffients... least squares fit can be applied here,
just as in polynomial fits.
Although I missed most of the thread, I hope you'll find this generalization
helpful.
-Aj

"AJ "no z" Johnson" <aj.jozhnson@lmco.com> wrote in message
news:cffpln$fkh1@cui1.lmms.lmco.com...
------SNIP
> Although I missed most of the thread, I hope you'll find this
generalization
> helpful.

groups.google.com

polyval fourier

will bring up the entire thread.

Hope this helps.

Greg