Repeated median regression

In robust statistics, repeated median regression, also known as the repeated median estimator, is a robust linear regression algorithm. The estimator has a breakdown point of 50%. Although it is equivariant under scaling, or under linear transformations of either its explanatory variable or its response variable, it is not under affine transformations that combine both variables. It can be calculated in $O(n^{2})$ time by brute force, in $O(n\log ^{2}n)$ time using more sophisticated techniques, or in $O(n\log n)$ randomized expected time. It may also be calculated using an on-line algorithm with $O(n)$ update time.

Method

The repeated median method estimates the slope of the regression line $y=A+Bx$ for a set of points $(X_{i},Y_{i})$ as

${\widehat {B}}={\underset {i}{\operatorname {median} }}\ {\underset {j\,\neq \,i}{\operatorname {median} }}\ \operatorname {slope} (i,j)$

where $\operatorname {slope} (i,j)$ is defined as $(Y_{j}-Y_{i})/(X_{j}-X_{i})$.

The estimated Y-axis intercept is defined as

${\widehat {A}}={\underset {i}{\operatorname {median} }}\ {\underset {j\,\neq \,i}{\operatorname {median} }}\ \operatorname {intercept} (i,j)$

where $\operatorname {intercept} (i,j)$ is defined as $(X_{j}Y_{i}-X_{i}Y_{j})/(X_{j}-X_{i})$.

A simpler and faster alternative to estimate the intercept ${\widehat {A}}$ is to use the value ${\widehat {B}}$ just estimated, thus:

${\widehat {A}}={\underset {i}{\operatorname {median} }}\ (y_{i}-{\widehat {B}}x_{i})$

Note: The direct and hierarchical methods of estimating ${\widehat {A}}$ give slightly different values, with the hierarchical method normally being the best estimate. This latter hierarchical approach is idential to the method of estimating ${\widehat {A}}$ in Theil–Sen estimator regression.

See also

• Theil–Sen estimator