6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 1: Using advanced tools from computational geometry, one can improve the running time to $\tilde{O}(n^{4/3})$.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.