Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 4 down vote favorite
1

I have a question related to linear function estimation. Suppose the potential line function model can be expressed as ax+by+c=0, where a, b, c are the unknown parameters that needed to be estimated. Now a set of data is given (x1,y1), (x2, y2), ... (xn, yn), and we want to make use of these data to estimate the parameters. As outliers (points that are not suited for model estimation) may exist in this data set, one way to avoid outliers is to minimize sum(abs(a*xi+b*yi+c)) (i=1,2, ..., n). However, I could not figure out how to minimize this function step by step, could anyone give me some clues? Thanks!

share|improve this question
1  
Have you looked at least squares estimation (en.wikipedia.org/wiki/Least_squares)? If so, why did you reject it in favor of using an L1 metric? – andand Sep 27 '12 at 16:10
1  
do you need just to estimate a model or do you necessarily have to use L1? In the first case you could simply use least squares with the function polyfit – Batsu Sep 27 '12 at 16:25
1  
@andand I have tried least squares method, but the problem with this method is that it is not robust to outliers. – feelfree Sep 27 '12 at 17:14

migrated from stackoverflow.com Sep 29 '12 at 0:50

3 Answers

up vote 3 down vote

Have you looked at L1-magic ? it's a Matlab package that contains code for solving seven optimization problems using L1 norm minimization. If I understand you correctly, you are looking for is also known as basis pursuit, a procedure that finds the vector with smallest L1 norm ||X_1|| := Sum |Xi| subject to AX = b, that explains the observations b. This can be done by implementing a primal-dual algorithm for linear programming (see S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004). A short explenation for doing this is found in section 2.1 of the L1-magic manual...

share|improve this answer
I believe this best answers feelfree's question, although others have suggested other possible solutions, this one addresses the L1 need. – macduff Sep 27 '12 at 16:58
up vote 1 down vote

There was a great solution to this same problem posted on this CrossValidated previously: L1 minimization cast as linear programming, that you can implement yourself.

share|improve this answer
up vote 0 down vote

Let

ax+by+c = 0

Then

a/b x + y + c/b = 0

and then

y = -a/b x - c/b

which is of the form

y = mx + b

and you are doing a simple fit to a straight line. The standard technique for doing this is least squares, which minimizes the mean squared error (the L2 norm).

Google "least squares Matlab".

The L2 norm is used, instead of the L1 norm, because the L2 norm is everywhere differentiable. The L1 norm is not, making minimization, which involves the derivative of the error function, problematic.

share|improve this answer
@StephenCanon, you're right. I've corrected my answer. Thank you. I'm getting old. – John R. Strohm Sep 27 '12 at 17:46
The question is explicitly asking for the L1 norm because he does not want the L2 norm. – Michael McGowan Sep 27 '12 at 18:13
The OP states that his data has outliers and therefore is completely unsuited to least-squares estimation. The quality of the resulting least-squares approximation could be horrendous – mathematician1975 Sep 28 '12 at 6:49

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.