# How far apart can L1 and L2 lines fit to the same data be?

Given $n$ points $(x_i, y_i)$ in the unit square with $x_i = {{i - 1} \over {n - 1}}$ uniformly spaced and $0 \leq y_i \leq 1$, consider the best-fit L1 line and the best-fit L2 line:

$\qquad$ L1 aka Least absolute deviation line: minimize $\sum |y_i - a_1 \, x_i - b_1|$
$\qquad$ L2 aka least squares or simple linear regression line: minimize $\sum (y_i - a_2 \, x_i - b_2)^2$

How far apart can these two lines be, over all sets of $n$ points $(x_i, y_i)$ as above ?

The following patterns of $y_i \in \{0, 1\}$ have L1 lines constant 0, which simplifies life. They are local maxima, > nearby patterns, but that doesn't prove anything.

• (1) Just out of curiosity, why don't you ask this on Cross-Validate? I can see you have been active over there for years, and I think this question can get better response there. (2) I think the tags "geometry" and "area" are totally wrong. The tag "approximation" is also wrong, as it should be "approximation theory". There are also tags "regression" and "regression analysis" here. Commented Jun 6, 2018 at 20:46
• @Lee David Chung Lin. 1) maybe so, but so far it's just a puzzle in finding 0-1 sequences (btw 010101 ... 0 works too). 2) thanks, done Commented Jun 7, 2018 at 14:39