# How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible.

I need a linear program description for minimizing L1 norm error

ie. Find the $a,b,c$ that Minimize $\sum^n_{i=1} |ax_i + by_i -c|$

Let $M_i=|ax_i + by_i - c|$ for $i \in \{1, ..., n\}$.

Minimize $\sum_i^n M_i$

Subject to: $-M_i \leq ax_i + by_i - c \leq M_i$ for each $i$

Is this correct?

-
You haven't clearly stated the problem. What is it that you want to max/minimize, under what constraints? – Omnomnomnom Jul 26 '13 at 22:06
If you put $M_i$ instead of $M$, your method seems ok to me. (The sentence "Let $M$ be max of ..." does not make sense.) – Tunococ Jul 26 '13 at 22:50
I updated my answer, does it look better now? – zeion Jul 26 '13 at 23:01
If you remove the line Let $M_i$ be the greatest sum of all $ax_i + by_i - c$ you have it. $M_i \geq$ for all $i$ is probably implicitly met, but it doesn't hurt to have it explicitly. – Peter Sheldrick Jun 27 '14 at 1:59
The formulation is correct! – vdesai Feb 9 at 21:10

You're mixing the infinity norm (where $M=\max_i |ax_i+by_i-c|$) with the 1-norm, where we take $M_i=|ax_i+by_i-c|$. In the case of the infinity norm, we can write $M\geq |ax_i+by_i-c|$ for each $i$, so you would get something similar for the constraints: $$-M\leq ax_i+by_i-c\leq M$$