The catline for deep regression

Motivated by the notion of regression depth (Rousseeuw and Hubert, 1996) we introduce the catline, a new method For simple linear regression. At any bivariate data set Z(n) = {(x(i), y(i)); i=1,...,n} its regression depth is at least n/3. This lower bound is attained For data lying on a convex or concave curve, whereas for perfectly linear data the catline attains a depth of n. We construct an O(n log n) algorithm for the catline, so it can be computed Fast in practice. The catline is Fisher-consistent at any linear model y=beta x+alpha+e in which the error distribution satisfies med(e\x)=0, which encompasses skewed and/or heteroscedastic errors. The breakdown value of the catline is 1/3, and its influence function is bounded. At the bivariate gaussian distribution its asymptotic relative efficiency compared to the L-1 line is 79.3 % for the slope, and 88.9 % for the intercept. The finite-sample relative efficiencies are in close agreement with these values. This combination of properties makes the catline an attractive fitting method. (C) 1998 Academic Press.