Fitting a line by minimizing absolute deviation

  • I
  • Thread starter borson
  • Start date
  • Tags
    math
  • #1
30
0

Main Question or Discussion Point

Hey guys!.
I need to use this method of minimization.
The procedure to follow is explained here:
http://es.tinypic.com/r/35mmtg0/9
However, I do not fully understand. What do I have to do?
What I got from the paper is that I only have to minimize the equation 15.7.16, by using bisection. With this I am supposed to obtain the parameter b, whilst "a" would be got by means of 15.7.15 once the former is minimized and we know the true b.
Then, do I not have to do anything with 15.7.14?
Is it correct what I stated of how to perform the method or I am mistaken?
Thank you all!
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,376
4,901
I only have to minimize the equation 15.7.16, by using bisection. With this I am supposed to obtain the parameter b, whilst "a" would be got by means of 15.7.15 once the former is minimized
No, you have to use both equations in finding b. For each trial value of b, use 15.7.15 to find the corresponding a, then evaluate the expression in 15.7.16. Adjust the choice of b according the "bracketing and bisection" procedure and repeat.
 
  • #3
30
0
No, you have to use both equations in finding b. For each trial value of b, use 15.7.15 to find the corresponding a, then evaluate the expression in 15.7.16. Adjust the choice of b according the "bracketing and bisection" procedure and repeat.
Thanks for replying!

Then 15.7.14 is not used at all?
 
  • #4
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,376
4,901
Thanks for replying!

Then 15.7.14 is not used at all?
.14 leads to, and is superseded by, the pair .15 and .16.
 
  • #5
30
0
.14 leads to, and is superseded by, the pair .15 and .16.
Perfect. I designed the algorithm to perform it in that way. The problem is though, that the signs of Fx for the different values of b to bisect, after just one iteration, are the same!. Then no bisection step is taken. I do not understand why this is happening as 1) the function I am minimizing must have a root, 2) The interval to bisect that I am choosing contains that root. I am confused.
Thanks!
 
  • #6
30
0
By the way. Can someone explain me what finding a root going downhill means?
And how can I minimize that function (.16) if its "y" values (I mean, fx) are all of the same sign? (they should have different sign so that bisection could be applied)
Is it possible to bisect in that case?

thank you all!
 
  • #7
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,376
4,901
Perfect. I designed the algorithm to perform it in that way. The problem is though, that the signs of Fx for the different values of b to bisect, after just one iteration, are the same!. Then no bisection step is taken. I do not understand why this is happening as 1) the function I am minimizing must have a root, 2) The interval to bisect that I am choosing contains that root. I am confused.
Thanks!
I'd need to see the data and some of the processing to figure out what is going wrong. Or maybe the coding?
 
  • #8
30
0
I'd need to see the data and some of the processing to figure out what is going wrong. Or maybe the coding?
I think the whole code would be a bit tedious to read. I have gone over it some hundred of times and there is no mistake in that.
here is the function that I have to minimize (43)
http://es.tinypic.com/r/2m2iebr/9

And here is the data. http://es.tinypic.com/r/d4l8j/9.
Altogether with the results of the bisection.
h2 is the parameter to be bisected, which in 43 is "n". (h is an array, composed by the different values that n gets during bisection)
I give a 0,1 - 400 interval to bisect, and as it is seen in the results, the three "n"s, yield the same result in the equation .16 (named Fx in my code), thus, no further bisection step is taken.
Thank you for all!
 
  • #9
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,376
4,901
here is the data
I cannot cut-and-paste from a screen snapshot. Please paste the data into a post as text.
 
  • #10
30
0
I cannot cut-and-paste from a screen snapshot. Please paste the data into a post as text.
Oh of course, sorry.

{0.75, 64.36 }, //Time of a turn, final space in radians
{1.383, 33.50 },
{1.5, 28.29 },
{1.7, 21.449},
{1.0, 51.36},
{0.85, 58.242 },
{1.35, 34.12 },
 
  • #11
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,376
4,901
Oh of course, sorry.

{0.75, 64.36 }, //Time of a turn, final space in radians
{1.383, 33.50 },
{1.5, 28.29 },
{1.7, 21.449},
{1.0, 51.36},
{0.85, 58.242 },
{1.35, 34.12 },
I find that to make the algorithm work you do need to start in the right ballpark.
Here are some values I got:
Code:
    b     a         sums
             15.7.16   15.7.14
-46.2 97.56  0.37       5.19
-46.4 97.76  0.37       5.27
-44   95.36 -0.93       7.09
-46   97.34 -0.78       5.24
-46.1 97.44 -0.13       5.18
-45   96.36 -0.93       6.16
-47   98.5   0.75       5.63
-45.5 96.86 -0.93       5.69
-46.5 97.86  0.37       5.3
So it is converging somewhere around b=-46.1.

Edit: I notice that it goes a bit crazy when one of the sgn() arguments is exactly zero. The recommended procedure of setting the value returned to zero does not fix it. Might be something to with the median function - that might need some tweaking. Look at b=-46.08.
 
Last edited:
  • #12
30
0
I find that to make the algorithm work you do need to start in the right ballpark.
Here are some values I got:
Code:
    b     a         sums
             15.7.16   15.7.14
-46.2 97.56  0.37       5.19
-46.4 97.76  0.37       5.27
-44   95.36 -0.93       7.09
-46   97.34 -0.78       5.24
-46.1 97.44 -0.13       5.18
-45   96.36 -0.93       6.16
-47   98.5   0.75       5.63
-45.5 96.86 -0.93       5.69
-46.5 97.86  0.37       5.3
So it is converging somewhere around b=-46.1.

Edit: I notice that it goes a bit crazy when one of the sgn() arguments is exactly zero. The recommended procedure of setting the value returned to zero does not fix it. Might be something to with the median function - that might need some tweaking. Look at b=-46.08.

which values for phi have you used? (I mean, for the second parameter to find out in equation 42) I already know its right phi value, which is 6.19
Still, using that value, my bisection does not work.
Thanks!
 
  • #13
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,376
4,901
which values for phi have you used? (I mean, for the second parameter to find out in equation 42) I already know its right phi value, which is 6.19
Still, using that value, my bisection does not work.
Thanks!
I just took the data values you posted (#10) as (x, y) pairs and applied the algorithm.
 

Related Threads for: Fitting a line by minimizing absolute deviation

Replies
3
Views
3K
  • Last Post
Replies
2
Views
5K
Replies
4
Views
2K
Replies
3
Views
23K
Replies
6
Views
54K
  • Last Post
Replies
8
Views
24K
Replies
1
Views
2K
  • Last Post
Replies
3
Views
4K
Top