Fitting a line by minimizing absolute deviation

[borson]

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!

 

[haruspex]

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.

 

[borson]

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?

 

[haruspex]

Thanks for replying!

Then 15.7.14 is not used at all?

.14 leads to, and is superseded by, the pair .15 and .16.

 

[borson]

.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!

 

[borson]

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!

 

[haruspex]

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?

 

[borson]

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!

 

[haruspex]

here is the data

I cannot cut-and-paste from a screen snapshot. Please paste the data into a post as text.

 

[borson]

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 },

 

[haruspex]

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:

    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.

 

[borson]

I find that to make the algorithm work you do need to start in the right ballpark.
Here are some values I got:

    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!

 

[haruspex]

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.