# Time complexity of simple linear regression in $L_1$ norm

I come from a computer science background. I'm considering simple linear regression using $$L_1$$ distance.

We are given points $$(x_1,y_1),\ldots,(x_n,y_n)\in \mathbb{R}^2$$. We are interested in finding a line $$f(x) = ax+b$$, such that

$$\sum_{i=1}^n |y_i - f(x_i)|$$ is minimized.

I did some initial literature search, and it seems people solve the problem using linear programming. I am interested in finding the fastest algorithm in terms of the number of points. That is, I'm looking for references that looks like the following

Simple linear regression in $$L_1$$ norm can be solved in $$O(T(n))$$ time, where $$n$$ is the number of points.

There is a $$O(n^2)$$ running time algorithm.

It is fairly easy to derive: There exists an optimal line that contains one of the given points (in fact, at least 2 points). There exists a $$O(n)$$ time algorithm to decide the best line that goes through a given point. Basically a weighted median computation. Together, it implies a $$O(n^2)$$ running time algorithm.

The first paper I know that uses this idea is the following.

Bloomfield, Peter; Steiger, William, Least absolute deviations curve-fitting, SIAM J. Sci. Stat. Comput. 1, 290-301 (1980). ZBL0471.65007.

Edit 2: There is a paper that gives a $$O(n\log^2 n)$$ time algorithm.

Megiddo, Nimrod; Tamir, Arie, Finding least-distance lines, SIAM J. Algebraic Discrete Methods 4, 207-211 (1983). ZBL0517.05007.

There is another paper which I still have to verify, that explains $$O(n)$$ time is possible. In fact, it seems that $$L_1$$ linear regression in $$d$$ dimensions can be solved in $$O(n)$$ time if $$d$$ is a constant.

Zemel, Eitan, An O(n) algorithm for the linear multiple choice knapsack problem and related problems, Inf. Process. Lett. 18, 123-128 (1984). ZBL0555.90069.