Least Median Squared (LmedSq) and
Least Median Absolute Deviation (LMedAbsDev)

Introduction

Given n points x₁, ... , x_n find a model M uniquely determined by p points which fits to the n points in a robust way.

Algorithm

1. Select randomly p points and use them to determine a model M. For a straight line, M is a straight line through two points.
2. For all points x_i, except the p points from step 1, calculate the deviation d_i of x_i from M. For a straight line, it is the euclidean distance from x_i to the line M.
3. Calculate the deviation measure d(M) for the model M as the median of d_i² (LMedSq), or the median of |d_i| (LMedAbsDev), for the d_i values found in step 2.
4. Execute step 1-3 many times, and choose the model M which has the least devaiation d(M) found in step 3.

A disadvantage of LMedSq is that it can only find a model determined by point in the data set x₁, ..., x_n. But outlines (noise points) can be sorted out before using the method of least squares. For a straight line fit, the robust estimate can be improved by minimizing the absolute deviation using the Least Absolute Deviation (LAbsDev) method [2].

References and resources

1. William H. Press, Daul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in C, 2nd edition. ISBN 0-521-43108-5, Cambridge University Press, 1992.
   
2. Numerical Recipes in C [1], section 15.7 (Robust Estimation) (PostScript, PDF).