Curve Fitting Problem

[A. Kalten]

Hello,

I need some advice on solving a curve fitting problem.

Ordinarily, a curve fitting algorithm, such as polyfit
or wpolyfit in octave, will determine the coefficients of a
polynomial that best fits the empirical data. If the model
is a second degree polynomial, a x^2 + b x + c, the algorithm
will return the best coefficients a, b, and c.

The trouble I am having is that I need to fit a second
degree polynomial where some of the coefficients are
either already known or include another known parameter
as a factor. For example, I need to find the best value
for k in this equation:

k^2/4 x + k p x + p^2

where p is a known quantity.

Although there are three coefficients, there is really
only one unknown parameter, that is k. Using polyfit from octave
will return a, b, and c where a = k^2/4, b = k p, and c = p^2.

Solving the two equations for k gives values that
are significantly different (they differ in the second
decimal place).

Is there an algorithm available that allows some of the
parameters of the model to be predetermined or to include
some predetermined factor?

I suspect that the only solution would be to write a
custom least squares program.

AK

[A. Kalten]

On Thu, 26 Jun 2008 16:47:57 -0700

AK, in your specific example (which I assume contains a typo and should
really be (k^2/4)x^2, since as written it's linear)
I don't see why you aren't just solving the linear regression for y =
(k/2)x + p
please explain what I'm missing

Yes, that was a typo and should be (k^2/4)x^2.

When dealing with data that has error terms any transformation
of the data to get a linear relation is generally not a good idea.

But even transforming the data to get the linear model still
leaves p, which is a known quantity. Functions such as
polyfit will expect both parameters to be unknown and
unconstrained.

I am looking for some off-the-shelf function that will allow
me to specify parts of the model and that will just determine
the unknown parameters. There do not seem to be any off-the-shelf
packages that will do this and probably the only recourse is
to do some custom programming.

AK

[Ben Abbott]

Post by A. Kalten
Hello,
I need some advice on solving a curve fitting problem.
Ordinarily, a curve fitting algorithm, such as polyfit
or wpolyfit in octave, will determine the coefficients of a
polynomial that best fits the empirical data. If the model
is a second degree polynomial, a x^2 + b x + c, the algorithm
will return the best coefficients a, b, and c.
The trouble I am having is that I need to fit a second
degree polynomial where some of the coefficients are
either already known or include another known parameter
as a factor. For example, I need to find the best value
k^2/4 x + k p x + p^2
where p is a known quantity.
Although there are three coefficients, there is really
only one unknown parameter, that is k. Using polyfit from octave
will return a, b, and c where a = k^2/4, b = k p, and c = p^2.
Solving the two equations for k gives values that
are significantly different (they differ in the second
decimal place).
Is there an algorithm available that allows some of the
parameters of the model to be predetermined or to include
some predetermined factor?
I suspect that the only solution would be to write a
custom least squares program.
AK

I assume you intended your example to be: k^2/4 * x^2 + k * p * x +
p^2 ?

On first inspection, it appears your example has non-linear constraints.

Is this example the specific problem you'd like to solve, or are you
looking for something a general solution?

Ben

[A. Kalten]

On Thu, 26 Jun 2008 21:14:12 -0400

Post by Ben Abbott
On first inspection, it appears your example has non-linear constraints.
Is this example the specific problem you'd like to solve, or are you
looking for something a general solution?

This is a specific problem, but there are/will be others of a similar
nature.

I am asking if there are off-the-shelf curve-fitting algorithms,
maybe for octave, that will allow constraints on some of the parameters,
or is custom programming the only way to go.

AK

[Ben Abbott]

Post by A. Kalten
On Thu, 26 Jun 2008 21:14:12 -0400

Post by Ben Abbott
On first inspection, it appears your example has non-linear
constraints.
Is this example the specific problem you'd like to solve, or are you
looking for something a general solution?

This is a specific problem, but there are/will be others of a similar
nature.
I am asking if there are off-the-shelf curve-fitting algorithms,
maybe for octave, that will allow constraints on some of the
parameters,
or is custom programming the only way to go.
AK

If the constraints are linear, then a general solution is possible. In
fact there is a free version available for Matlab (although I don't
know what sort of license is involved).

If the constraints are non-linear (as in your example) then the
difficulty of a solution will depend upon whether or not the variables
are pure real or complex valued.

Ben

[Sergei Steshenko]

Applications

[A. Kalten]

On Thu, 26 Jun 2008 19:52:32 -0700 (PDT)

If I understand your problem correctly, is more or less like this;
1) there is f(x) to be approximated;
a * x^2 + b * x + c;

In this case there is no function to be approximated. There
is only data that fits a theoretical model. I was inquiring
about any off-the-shelf algorithms that can fit a function
to a data set where some of the parameters of the function
need to be constrained in a certain way.

AK

[Abdul Rahman Riza]

Dear Friends,

Anybody can figure out how powerffull octave to tacke image processing
problem?

Riza

No virus found in this outgoing message.
Checked by AVG.
Version: 7.5.524 / Virus Database: 270.4.1/1521 - Release Date: 6/26/2008
11:20 AM

[Søren Hauberg]

Post by Abdul Rahman Riza
Anybody can figure out how powerffull octave to tacke image processing
problem?

A lot of people use Octave for image processing, so I think the answer
is yes :-)
If you want help you need to ask more specific questions, as nobody
can answer a question that haven't been asked.

Søren

[Abdul Rahman Riza]

Dear Friends,

I follow instruction from octave tutorial as following

octave:1> I = loadimage ("default.img");
octave:2> S = conv2 (I, ones (5, 5) / 25, "same");
octave:3> [Dx, Dy] = gradient (S);
octave:4>

what next..??

I am a newbie here but I want to input an image, do a simple opreration,
display its result and save it.

Anybody can give me a simple example?

Riza

Post by Søren Hauberg

Anybody can figure out how powerfull octave to tacke image processing
problem?

A lot of people use Octave for image processing, so I think the answer
is yes :-)
If you want help you need to ask more specific questions, as nobody
can answer a question that haven't been asked.
Søren

[s***@hauberg.org]

Post by Abdul Rahman Riza
I follow instruction from octave tutorial as following
octave:1> I = loadimage ("default.img");
octave:2> S = conv2 (I, ones (5, 5) / 25, "same");
octave:3> [Dx, Dy] = gradient (S);
octave:4>
what next..??
I am a newbie here but I want to input an image, do a simple opreration,
display its result and save it.

If you then do

grad_len = sqrt (Dx.^2 + Dy.^2);
imshow (grad_len, [])

then you should get a gradient image (i.e. something that highlights
edges). If you install the 'image' package from OctaveForge
(http://octave.sf.net) then you'll get a bunch of functions that'll
allow you to do more interesting things.
One example would be somthing like

E = edge (I);
imshow (E)

which will detect edges and display them. But unless you mention a
specific problem you want to solve I can't give you better examples.

If you install the 'image' packagem, you'll be able to save your results using

imwrite ("test.png", E);

Hope that helps,
Søren

Post by Abdul Rahman Riza
Anybody can give me a simple example?
Riza

Post by Søren Hauberg

Anybody can figure out how powerfull octave to tacke image processing
problem?

A lot of people use Octave for image processing, so I think the answer
is yes :-)
If you want help you need to ask more specific questions, as nobody
can answer a question that haven't been asked.
Søren

[Jaroslav Hajek]

Post by A. Kalten
On Thu, 26 Jun 2008 19:52:32 -0700 (PDT)

If I understand your problem correctly, is more or less like this;
1) there is f(x) to be approximated;
a * x^2 + b * x + c;

In this case there is no function to be approximated. There
is only data that fits a theoretical model. I was inquiring
about any off-the-shelf algorithms that can fit a function
to a data set where some of the parameters of the function
need to be constrained in a certain way.

I think there are at least two implementations of the
levenberg-marquardt algorithm in OctaveForge's optim package. Having a
matlab-compatible lsqnonlin in Octave would be good. In general,
making the optimization stuff more systematic and matlab-compatible is
a worthy long-term goal.
It's on my TODO list, too :) A couple of months ago I have proposed to
include also other parts of MINPACK (which is employed for fsolve) to
implement lsqnonlin. I was ready to volunteer for this project (which
would benefit me as well). However, JWE suggested that Octave could
employ GSL in the future, which has the MINPACK algorithms rewritten
in C,
in a reentrant and safe way. On the contrary, making MINPACK reentrant
(which I think is desirable) would involve modifying the code.
I have thus decided to postpone any work on the optimization routines
until the future of GSL in Octave is clear. GSL would probably allow
us to get rid of much (if not all) of libcruft, however, it has its
problems as well. One thing is that GSL does not support floats
(single precision) almost anywhere; now that Octave supports them that
could cause problems.
Also, GSL cannot (not even optionally) employ LAPACK for linear
algebra (which is faster and more elaborate than GSL's own LA stuff).
I am not aware of the status of GSL in Octave at this moment.

regards

Post by A. Kalten
AK
_______________________________________________
Help-octave mailing list
https://www.cae.wisc.edu/mailman/listinfo/help-octave

[A. Kalten]

On Fri, 27 Jun 2008 07:34:35 +0200

Post by Jaroslav Hajek
Having a
matlab-compatible lsqnonlin in Octave would be good. In general,
making the optimization stuff more systematic and matlab-compatible is
a worthy long-term goal.

The Matlab lsqnonlin did the job for me. It allows some or all of
the coefficients of the model to be constrained. If very tight bounds
(e.g. +/- 1e-6) are placed on a coefficient, it is the same as fixing
the coefficient to that value.

But thanks to everyone who responded. I will certainly keep all
the suggestions in mind. That is the value of this list. One can
learn a great deal by encountering other perspectives.

AK

[Peter Cloetens]

My suggestions would be:
either:
treat this as a non-linear fitting problem with 1 unknown and use for
example "leasqr" from the octave-forge package optim
or:
solve explicitly for your unknown "k" and you end up with an explicit
solution.
Something like:
Minimize the cost function
cost(k) = sum |y_i - k^2/4*x_i^2 - k*p*x_i - p^2|^2
with respect to k
Derivation leads to a cubic (third order) equation in k:
a*k^3 + b*k^2 +c*k + d = 0
with
a = 1/8*sum(x_i^4)
b = 3/4*p*sum(x_i^3)
c = 3/2*p^2*sum(x_i^2) - 1/2*sum(y_i*x_i^2)
d = -p*sum(y_i*x_i) + p^3*sum(x_i)
The cubic equation can be solved with the octave function fzero or
explicitly with one of the methods described here:
http://en.wikipedia.org/wiki/Cubic_equation

Peter

Post by A. Kalten
Hello,
I need some advice on solving a curve fitting problem.
Ordinarily, a curve fitting algorithm, such as polyfit
or wpolyfit in octave, will determine the coefficients of a
polynomial that best fits the empirical data. If the model
is a second degree polynomial, a x^2 + b x + c, the algorithm
will return the best coefficients a, b, and c.
The trouble I am having is that I need to fit a second
degree polynomial where some of the coefficients are
either already known or include another known parameter
as a factor. For example, I need to find the best value
k^2/4 x + k p x + p^2
where p is a known quantity.
Although there are three coefficients, there is really
only one unknown parameter, that is k. Using polyfit from octave
will return a, b, and c where a = k^2/4, b = k p, and c = p^2.
Solving the two equations for k gives values that
are significantly different (they differ in the second
decimal place).
Is there an algorithm available that allows some of the
parameters of the model to be predetermined or to include
some predetermined factor?
I suspect that the only solution would be to write a
custom least squares program.
AK
_______________________________________________
Help-octave mailing list
https://www.cae.wisc.edu/mailman/listinfo/help-octave

[Sergei Steshenko]

Applications

[Fredrik Lingvall]

Post by A. Kalten
Hello,
I need some advice on solving a curve fitting problem.
Ordinarily, a curve fitting algorithm, such as polyfit
or wpolyfit in octave, will determine the coefficients of a
polynomial that best fits the empirical data. If the model
is a second degree polynomial, a x^2 + b x + c, the algorithm
will return the best coefficients a, b, and c.
The trouble I am having is that I need to fit a second
degree polynomial where some of the coefficients are
either already known or include another known parameter
as a factor. For example, I need to find the best value
k^2/4 x + k p x + p^2
where p is a known quantity.
Although there are three coefficients, there is really
only one unknown parameter, that is k. Using polyfit from octave
will return a, b, and c where a = k^2/4, b = k p, and c = p^2.
Solving the two equations for k gives values that
are significantly different (they differ in the second
decimal place).
Is there an algorithm available that allows some of the
parameters of the model to be predetermined or to include
some predetermined factor?
I suspect that the only solution would be to write a
custom least squares program.
AK

AK,

Do you have any prior information of the parameter k? Do you, for
example, know if k is positive, or do you have any idea how much it may
vary (variance of k), mean value, if k is bound to some interval, etc?

An idea is then to formulate the problem as a parameter estimation problem, using the model

y = k^2/4 x^2 + k p x + p^2 + e

where e "describes" the misfit of the model. Say, for example, that you know that k is in the interval [a,b] and by assuming Gassian errors, e,
you can find the most likely k (i.e, the maximum a posteriori estimate) by finding the k which maximizes


\hat{k} = arg max { exp (-1/ (2 sigma_e^2) ( Y-k^2/4 X.^2 + k p X +
p^2)^T ( Y-k^2/4 X.^2 + k p X + p^2) ) }
k

for k in [a,b] where Y is the data vector Y =[y(1) y(2) ... y(N)]^T. If
you instead have knowledge of the mean and variance of k then you can
assign a Gaussian prior for k which will result in a different
(unbounded) optimization problem.

/Fredrik