Re: Least Absolute Deviations by Repeated Weighted Least-Squares - HELP!


Thanks for the reply!

That is reassuring to hear, since the first thing I did try was using an Epsilon value to avoid divide by zero errors, but it still converged to what seemed to be an incorrect local minimum. I had then switched to removing the points under epsilon.

By any chance, do any of you have a link to the Barrodale-Roberts algorithm?? I have not been able to find it.

And, I will post my source code here for sure if I cannot figure out this problem. It is Java.

Thanks again!


dontspam@xxxxxxxxxxx wrote:
>Hi all,
>
>A while back I neeed to implement a Least Absolute Deviations (LAD)
>algorithm. Some had suggested an iterative Weighted Least Squares
>procedure, with each point (Xi, Yi) having a weight being 1 / | Yi - B
>- M*Xi |. (a.k.a. 1 / (the abs. val. of the residual) )

Note that you have to be careful. If by chance the residual is zero,
you'll get a division by 0. If the residual is very small, then the
weight will be very large and this causes problems. One solution to
this is to use a weight of 1/| Yi-B-M*Xi | unless | Yi-B-M*Xi |<epsilon.
If | Yi-B-M*Xi |<epsilon, then use a weight of 1/epsilon. Simply
leaving the point out of the calculations doesn't sound like an
appropriate way to deal with this situation- I think it gives an
effective weight of 0!

Without seeing your code, it's impossible to know where the bug is.
I'd guess that you aren't properly handling the situation where there
is a very small residual at some stage of the computations. Your code
could still work well on problems where the near zero residual never
occurs.

>I'm testing the algorithms on 4 data sets. 3 of them produce the
>desired results, but one doesn't. Set 2 below does not work. Here are
>the sets and the acutal LAD regression lines, using a separate,
>correct program. "SAE" is the sum of absolute errors (what I want to
>minimize).

> Set 2: x: -2 -1 0 1 2
> y: -1.2 -1.1 0.3 0.8 1.55
>
> Y=.6875*X+.175, SAE=.775
>

My implementation of IRLS uses the technique described above with
epsilon=1.0e-6 and gets Y=0.6875*X+0.1750.










--
Brian Borchers borchers@xxxxxxx
Department of Mathematics http://www.nmt.edu/~borchers/
New Mexico Tech Phone: 505-835-5813
Socorro, NM 87801 FAX: 505-835-5366



.

Relevant Pages

  • Re: markov chain decomposition (nearly completely decomposable system)
    ... the chain has k-1 communicating ... approximately true for small epsilon. ... converges to zero. ... > with a probability transition matrix P having the following structure: ...
    (sci.math)
  • Re: how to prove that f^2+f ^2 <=1 if ...
    ... So let x now be a regular point of f: ... that epsilon has been taken to be smaller than F = f'^2. ... That is one half of the desired inequality. ... But since x- is a point, where f' takes a value very near to zero, ...
    (sci.math)
  • Re: Possible proof of Gabriels Theorem?
    ... >> that delta must eventually become zero, however, according to the ... No infinitesimals. ... Nothing indeed about epsilon being small. ...
    (sci.math)
  • Re: Zero Content
    ... Let be a convergent sequence in R. Show that the set ... convergent sequence then there exist an epsilon s.t. length of I_k < ... is a subset of the union of those intervals. ... No. What's the definition of "zero content"? ...
    (sci.math)
  • Re: Power Spectrum from Autocorrelation vs. FFT
    ... Simple natural phenomena are often mind benders...are ... weight per unit length* a piece of zero length has zero weight. ...
    (comp.dsp)