Thread Subject: How to sample less points and interpolate this curve?

Hi all,

Please take a look at this curve...

http://img211.imageshack.us/img211/375/qqqrq3.jpg

What is the best interpolation scheme for it? The purpose is to sample
as few number of points as possible....

Luna Moon wrote:

> Hi all,
>
> Please take a look at this curve...
>
> http://img211.imageshack.us/img211/375/qqqrq3.jpg

This curve looks like somebody's homework, isn't it?

> What is the best interpolation scheme for it?

There are three very best schemes:

1. Do it yourself
2. Hire a consultant
3. The ultimate interpolation scheme satisfying all of the possible
conditions and constraints


> The purpose is to sample
> as few number of points as possible....

Are you sure?


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

Luna Moon wrote:
> Hi all,
>
> Please take a look at this curve...
>
> http://img211.imageshack.us/img211/375/qqqrq3.jpg
>
> What is the best interpolation scheme for it? The purpose is to sample
> as few number of points as possible....

Again, far too little information and far too vague a request...

Interpolation over what region(s) of the curve, what accuracy required,
why interpolate instead of compute a value from what is obviously a
generated curve, etc., etc., etc., ad nauseum...

For a representative range of general interpolation techniques see
Chapter 25 of Abramowitz and Stegun.

--

Luna Moon wrote:
> Hi all,
>
> Please take a look at this curve...
>
> http://img211.imageshack.us/img211/375/qqqrq3.jpg
>
> What is the best interpolation scheme for it? The purpose is to sample
> as few number of points as possible....

What do you want to do? If you fit an equation to the curve, you won't
need to sample at all.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

On Sep 11, 12:42 pm, Luna Moon <lunamoonm...@gmail.com> wrote:
> Hi all,
>
> Please take a look at this curve...
>
> http://img211.imageshack.us/img211/375/qqqrq3.jpg
>
> What is the best interpolation scheme for it? The purpose is to sample
> as few number of points as possible....

Looks like a sinc function (Asin(x/T)/x). Are you assuming a model
(say, a sinc) and then trying to sample some points and then do a
regression to find the sinc that fits your data? Do your sampled
points have any noise in them? If you know the function is a sync,
and you know for certain only two pairs of x,y points, then I think
you can figure out all the parameters for the sinc function. If
there's noise, you'll need to do a regression (curve fitting).
Regards,
ImageAnalyst

On Sep 12, 4:31 am, ImageAnalyst <imageanal...@mailinator.com> wrote:

> Are you assuming a model
> (say, a sinc) and then trying to sample some points and then do a
> regression to find the sinc that fits your data?

sample points it seems to me almost easy, especially if the image has
no noise (just a thresholding), but, once we know the points, let say
we have a list of (x,y) coordinates, how to apply the regression?
Could you please explicitate that (with a simple example, maybe)? And
also (in partctice) is it computationally fast?
Do you know any library to do that? (let's say in C++, but also matlab
can be interesting)

cheers,
Mauro

mauro <mauro.australia@gmail.com> writes:

> On Sep 12, 4:31 am, ImageAnalyst <imageanal...@mailinator.com> wrote:
>
> > Are you assuming a model
> > (say, a sinc) and then trying to sample some points and then do a
> > regression to find the sinc that fits your data?
>
> sample points it seems to me almost easy, especially if the image has
> no noise (just a thresholding), but, once we know the points, let say
> we have a list of (x,y) coordinates, how to apply the regression?
> Could you please explicitate that (with a simple example, maybe)? And
> also (in partctice) is it computationally fast?
> Do you know any library to do that? (let's say in C++, but also matlab
> can be interesting)

For example, in Maple you could use LSSolve in the Optimization package
to do a nonlinear least-squares fit. Thus:

> pts:= [[1, 2.638017470], [2, -1.040091423], [3, -.2108976398],
         [4, .8159107623], [5, -.4113129790], [6, -.3618112451],
         [7, .4473323711], [8, -.6082768715e-1],
         [9, -.2272235211], [10, .3064095903]];
> Optimization[LSSolve](map(p -> p[2]-a*sin(b*p[1])/p[1], pts));

[.20432745885588e-1, [a = 2.92161285960735828, b = 1.99952669062360044]]

So Maple is saying that the best fit it can find to y = a*sin(b*x)/x
for these data is with a and b as above.
--
Robert Israel israel@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

mauro wrote:
> On Sep 12, 4:31 am, ImageAnalyst <imageanal...@mailinator.com> wrote:
>
>> Are you assuming a model
>> (say, a sinc) and then trying to sample some points and then do a
>> regression to find the sinc that fits your data?
>
> sample points it seems to me almost easy, especially if the image has
> no noise (just a thresholding), but, once we know the points, let say
> we have a list of (x,y) coordinates, how to apply the regression?
> Could you please explicitate that (with a simple example, maybe)? And
> also (in partctice) is it computationally fast?
> Do you know any library to do that? (let's say in C++, but also matlab
> can be interesting)

Note that the key is the model you assume.
When x = 0 then slope of sinc(x) is zero.
Looking at the graph, this doesn't look seem
to be the case to me. A different model may
therefore be more appropriate, something like:
     y = a*exp(-b*x)*cos(c*x)

However, the model should come from the
underlying physics, not from guessing.

--
Regards,
Martin Leese
E-mail: please@see.Web.for.e-mail.INVALID
Web: http://members.tripod.com/martin_leese/

On Sep 16, 4:05 pm, Martin Leese <ple...@see.Web.for.e-mail.INVALID>
wrote:
> mauro wrote:
> > On Sep 12, 4:31 am, ImageAnalyst <imageanal...@mailinator.com> wrote:
>
> >> Are you assuming a model
> >> (say, a sinc) and then trying to sample some points and then do a
> >> regression to find the sinc that fits your data?
>
> > sample points it seems to me almost easy, especially if the image has
> > no noise (just a thresholding), but, once we know the points, let say
> > we have a list of (x,y) coordinates, how to apply the regression?
> > Could you please explicitate that (with a simple example, maybe)? And
> > also (in partctice) is it computationally fast?
> > Do you know any library to do that? (let's say in C++, but also matlab
> > can be interesting)
See Levenberg-Marquardt and BFGS optimization methods. Numerical
Recipes in C or C++ cover these topics. Scilab has both. I would bet
Matlab does too. I didn't post before because Luna Moon was looking
for the easy answer and there aren't any if you dig into optimization
or data fitting at this level.

>
> Note that the key is the model you assume.
> When x = 0 then slope of sinc(x) is zero.
Yes, Robert Israel's solution requires a phase parameter if it was
meant to solve Luna Moon's problem. I think his example is just meant
to be an example of how few points are required to find a solution to
his data set. I bet the optimizing routine took about 6 to 10
iterations to find that solution.

I have written a few auto tuning routines and one of the main parts is
system identification. The customer is going to have NO clue as to
what model is best so you try many and look for the one that has the
best fit within reason. I have found that adding more parameters will
give the optimization routine more options to find better solutions
but not all of them make sense. That is the art like writing a chess
program.

> Looking at the graph, this doesn't look seem
> to be the case to me. A different model may
> therefore be more appropriate, something like:
> y = a*exp(-b*x)*cos(c*x)
You too made an assumption. I would add a phase and offset to both
yours and Robert Israel's equation and try them both and use the best
one. I would add a phase and offset because I couldn't tell by
looking Luna Moon's data if the phase and offset when x= 0 is zero.

Back to the number of points. Once one leaves the text books for
reality there is noise and measurements errors. Then it is best to
have many points because this will statistically reduce the model
error. Our auto tuning will use between 500 and 2000 points. This
takes a second or less depending on the data and the number of
points.
>
> However, the model should come from the
> underlying physics, not from guessing.
You guessed with your y=a*exp(-b*x)*cos(c*x).

There is an art to 'guessing.' In the real world, how are you going
to know what the form of the model is? Unless you know for sure you
should try many models and choose the best one by choosing the model
with the lowest norm or sum of squared error tempered by common sense.

I would have been impressed if Maple could have identified the form or
map of the model.

Peter Nachtwey