Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 '15 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 $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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