4
$\begingroup$

I have some points in 2D space and simply want to fit a line through them (solve for $m$ and $b$ of the equation $y = mx + b$) such that the maximum error for any given point is as small as possible. This is not least-squares linear regression because my goal is not to minimize the total error among all points. Instead, I want to minimize the error of the point that has the worst fit. Is there an equation for how to do this?

$\endgroup$

2 Answers 2

5
$\begingroup$

In least squares linear regression you are minimizing the L^2 norm of residuals. What you would like to do is to minimize the L^infinity norm. If you do not mind to have an approximate solution, you can minimize the L^p norm for a large p (say p=100, which should be a good approximation of infinity) and do it numerically with standard gradient methods.

$\endgroup$
1
  • $\begingroup$ +1 because this is definite a good point (that the OP is actually looking to minimize the infinity norm) but you could expand on it a bit more. $\endgroup$
    – usεr11852
    Feb 20, 2016 at 23:41
1
$\begingroup$

It can be formulated as a linear program and solved using techniques from operations research. A reference is "Linear Optimization and Extensions: Problems and Solutions," by Alevras and Padberg. They call it Chebycheff regression.

$\endgroup$
1
  • $\begingroup$ Should that be "Chebysheff"? I've seen about a dozen variant transliterations before (Chebyshev, Chebysheff, Chebyshov, Tchebychev, Tchebycheff, Tschebyschev, Tschebyschef, Tschebyscheff, Tschebyschow or Tschebyschew) but "Chebycheff", though feasible, would be a new one on me! $\endgroup$
    – Silverfish
    Feb 20, 2016 at 21:10

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.