Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$ be the greatest sum of all $ax_i + by_i - c$ for each $(x_i, y_i), 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|improve this question
1  
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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.