Deepest regression line

In this chapter we present an first algorithm to find the deepest regression line, which is the fit with maximal regression depth for a given dataset $Z_n = \{(x_i, y_i), i = 1,...,n \} \subset \rm I\!R^2$


Algorithm

Algorithm: Deepest regression line
Input:
  • $Z_n = \{(x_i, y_i), i = 1,...,n \} \subset \rm I\!R^2$
Steps:
  1. Sort all element of $Z_n$ by their $x$ coordinate such that $x_1 < x_2 < ... < x_n$
  2. For each pair $ij$ such that $0 < i < j \le n$:
    • Find the line $l_{ij}$ that intersects with observations $i$ and $j$
    • Use the algorithm defined in chapter two to compute $r_{ij} = rdepth(l_{ij}, Z_n)$ (without the sorting wich is already done)
    • If $r_{ij}$ is greater than the regression depth of the temporary solution, keep $l_{ij}$ as a new temporary solution.
  3. Return the $l_{ij}$ that has the greatest regression depth, it is the deepest regression line.

Given the previous algorithm, one can find the deepest regression line of a dataset $Z_n$ in $\mathcal{O}(n^3)$.

So we conclude thaht the algorithm presented in this chapter to compute the deepest regression line performs in $\mathcal{O}(n \log(n) + n^3) = \mathcal{O}(n^3)$.

Example

The following application allows you to find the deepest regression line of a set of points. Some random points can also be added to ease the use of the application.