| Author |
Message |
Guest
|
 Posted:
Wed Dec 14, 2005 1:04 am Post subject:
Closest Curve Fit with positive errors |
|
|
Hello,
I wish to fit certain points of a function to a simple curve (for my
current implementation, even a linear fit would suffice). The problem
is that I want my curve to be always above the function, i.e the error
(Curve - function) should be positive at all points.
Is there any hard and fast solution to solve the problem with this
constraint?
Would this be a good solution?
Get the value of the maximum '-ve' error with the least-squares fit and
simply add a constant value to the least-squares fit?
Thanks in advance
Raja |
|
| Back to top |
|
 |
Guest
|
| Posted:
Wed Dec 14, 2005 1:16 am Post subject:
Re: Closest Curve Fit with positive errors |
|
|
abariska@student.ethz.ch wrote:
| Quote: | I am assuming that you have N two dimensional points (x_k, y_k),
0<=k<N, which I would call the data, and that you wish to find some
kind of regression function f, such that the weighted error sum
sum_k g(f(x_k) - y_k)
is minimized under the constraint
f(x_k) - y_k >= 0, for 0 <= k < N
for some error weighting function g. g(x) = abs(x) would be L_1 error,
g(x) = x^2 would be L_2 error, etc.
|
Yes. your assumptions are correct. As far as the distance metric is
concerned i just care about the L1 norm. However, in this case g(x)
=abs(x) would be same as g(x)= x, as i want x to be positive due to
the constraint of positive error.
| Quote: | Certainly not optimal in any sense. Before I write any more, tell me
whether my assumptions above are correct.
|
I'm basically trying to fit a cumulative distribution function. So I do
not want the errors to be negative as they might cause non-zero
probabilities to be assigned zero probabilities. Positive errors will
alter non-zero probabilities by a small amount and i'm ok with that.
Thanks, I hope the i've made it clearer.
Raja |
|
| Back to top |
|
|
Guest
|
| Posted:
Wed Dec 14, 2005 1:16 am Post subject:
Re: Closest Curve Fit with positive errors |
|
|
ysriraja@gmail.com wrote:
| Quote: | Hello,
I wish to fit certain points of a function to a simple curve (for my
current implementation, even a linear fit would suffice). The problem
is that I want my curve to be always above the function, i.e the error
(Curve - function) should be positive at all points.
|
I am assuming that you have N two dimensional points (x_k, y_k),
0<=k<N, which I would call the data, and that you wish to find some
kind of regression function f, such that the weighted error sum
sum_k g(f(x_k) - y_k)
is minimized under the constraint
f(x_k) - y_k >= 0, for 0 <= k < N
for some error weighting function g. g(x) = abs(x) would be L_1 error,
g(x) = x^2 would be L_2 error, etc.
| Quote: |
Is there any hard and fast solution to solve the problem with this
constraint?
|
You don't mention any error weighting, so I assume you want to choose
g(x) to simplify the problem at hand.
| Quote: |
Would this be a good solution?
Get the value of the maximum '-ve' error with the least-squares fit and
simply add a constant value to the least-squares fit?
|
Certainly not optimal in any sense. Before I write any more, tell me
whether my assumptions above are correct.
Regards,
Andor |
|
| Back to top |
|
|
Fred Marshall
Guest
|
| Posted:
Wed Dec 14, 2005 9:15 am Post subject:
Re: Closest Curve Fit with positive errors |
|
|
<ysriraja@gmail.com> wrote in message
news:1134514233.070078.41600@g49g2000cwa.googlegroups.com...
| Quote: |
abariska@student.ethz.ch wrote:
I am assuming that you have N two dimensional points (x_k, y_k),
0<=k<N, which I would call the data, and that you wish to find some
kind of regression function f, such that the weighted error sum
sum_k g(f(x_k) - y_k)
is minimized under the constraint
f(x_k) - y_k >= 0, for 0 <= k < N
for some error weighting function g. g(x) = abs(x) would be L_1 error,
g(x) = x^2 would be L_2 error, etc.
Yes. your assumptions are correct. As far as the distance metric is
concerned i just care about the L1 norm. However, in this case g(x)
=abs(x) would be same as g(x)= x, as i want x to be positive due to
the constraint of positive error.
Certainly not optimal in any sense. Before I write any more, tell me
whether my assumptions above are correct.
I'm basically trying to fit a cumulative distribution function. So I do
not want the errors to be negative as they might cause non-zero
probabilities to be assigned zero probabilities. Positive errors will
alter non-zero probabilities by a small amount and i'm ok with that.
Thanks, I hope the i've made it clearer.
|
Have you considered the L-infinity or minimax norm? That seems better
suited to what you want to do. L1 or L2 will have nonuniform errors so
you'll have to bias the result according to the worst case.
I've done this successfully (without having proof of convergence):
Compute a minimax approximation using the Remez algorithm and don't worry
about the approximant going negative in the first or succeeding iterations.
However, do this:
At each iteration the algorithm selects a set of maxima in the error.
The points where these maxima exist will be the new points on which the
error will be equalized.
Here is the modification to the algorithm:
Save the new value of the equalized error.
Add 1/2 the magnitude of this value to the objective function - this moves
the objective function slightly upward away from zero.
Do this at each iteration.
Since, at each iteration, the equalized error will increase, the objective
function will move further and further away from zero. Probably less and
less at each step.
In the end, the error will alternate around a line that is equal to the peak
error.
So, negative peaks of the error will just equal zero and there will be no
negative error values.
I've used this as the first step in using Schussler's method of realizing
nonminimum phase filters - which starts with an optimum all-positive
response filter and takes its square root. So, the stop bands must be all
positive before taking the square root.
If there are multiple stop bands with different weights, then the objective
function in each stop band can be modified separately or according to the
weights.
Fred |
|
| Back to top |
|
|
Guest
|
| Posted:
Wed Dec 14, 2005 5:16 pm Post subject:
Re: Closest Curve Fit with positive errors |
|
|
ysriraja@gmail.com wrote:
| Quote: | abariska@student.ethz.ch wrote:
I am assuming that you have N two dimensional points (x_k, y_k),
0<=k<N, which I would call the data, and that you wish to find some
kind of regression function f, such that the weighted error sum
sum_k g(f(x_k) - y_k)
is minimized under the constraint
f(x_k) - y_k >= 0, for 0 <= k < N
for some error weighting function g. g(x) = abs(x) would be L_1 error,
g(x) = x^2 would be L_2 error, etc.
Yes. your assumptions are correct. As far as the distance metric is
concerned i just care about the L1 norm. However, in this case g(x)
=abs(x) would be same as g(x)= x, as i want x to be positive due to
the constraint of positive error.
|
If you want to fit a polynomial f of order p, f(x) = a_0 + a_1 x + ...
+ a_p x^p, then the errors e_k := f(x_k) - y_k are linear in the (p+1)
coefficients of the polynomial, and therefore the target function
sum_k e_k
and the constraints
e_k >= 0
are too. This is a classical linear programming problem. There are
quite a few readily available algorithms to solve this, the most famous
is the simplex method. Whether polynomials are a good choice as
regression functions depends on the behaviour you need outside the
interval [min(x_k), max(x_k)].
| Quote: | I'm basically trying to fit a cumulative distribution function.
|
I'm curious: how does solving the above problem result in the fit of a
distribution function?
Regards,
Andor |
|
| Back to top |
|
|
Guest
|
| Posted:
Wed Dec 14, 2005 5:16 pm Post subject:
Re: Closest Curve Fit with positive errors |
|
|
Thanks for the suggestions. I'll try them out.
Raja |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in