We know that simple linear regression will do the following thing:

Suppose there are $n$ data points $\{y_i,x_i\}$, where $i=1,2,\dots,n$. The goal is to find the equation of the straight line

$y=\alpha+\beta x$

which provides a best fit for the data points. Here "best" will be be understood as in the least-squares approach: such a line that minimizes the sum of squared residuals of the linear regression model. In other words, numbers $\alpha$ and $\beta$ solve the following minimization problem:

Find $\underset{{\alpha,\beta}}{\arg\min}\;Q(\alpha,\beta)$, where $Q(\alpha,\beta)=\sum\limits_{i=1}^n(y_i-\alpha-\beta x_i)^2$

My question is: if I want to minimize the following function, how to get $\alpha, \beta$:

$\underset{{\alpha,\beta}}{\arg\min}\;P(\alpha,\beta)$, where $P(\alpha,\beta)=\max\limits_{1\leq i\leq n} |y_i-\alpha-\beta x_i|$

  • $\begingroup$ I think the summand should be: $(y_i - \alpha -\beta x_i)^2$, and same in the expression of $P(\alpha, \beta)$. $\endgroup$ – AlbertH Jun 27 '11 at 9:48
  • $\begingroup$ @AlbertH Thank you for correcting, I have modified the bug. $\endgroup$ – Fan Zhang Jun 27 '11 at 9:54
  • $\begingroup$ I think you mean $\text{argmin}$ where you write $\min$ -- the goal is to find $\alpha$ and $\beta$, not the values of the objective function. $\endgroup$ – joriki Jun 27 '11 at 10:51
  • $\begingroup$ @joriki I have modified the bug, thx. $\endgroup$ – Fan Zhang Jun 27 '11 at 12:50

You're asking about doing linear regression with the $L_{\infty}$ norm or, equivalently, the Chebyshev approximation criterion, rather than the usual $L_2$ norm that minimizes the sum of squared residuals.

There isn't a nice formula that will give you $\alpha$ and $\beta$. Instead, the standard approach is to obtain $\alpha$ and $\beta$ as the solution to a linear programming problem. The formulation is

$$\text{Minimize } r$$

subject to $$r - (y_i - \alpha - \beta x_i ) \geq 0, \text{ for each } i,$$ $$r + (y_i - \alpha - \beta x_i ) \geq 0, \text{ for each } i.$$ The variables are $r$ (the maximum residual), $\alpha$, and $\beta$, and the $(x_i, y_i)$ are the data values that become parameters in the LP formulation.

Here's an example, although the author assumes a model with $\alpha = 0$.

  • 1
    $\begingroup$ In fact, due to the special structure of the problem, the simplex method can be simplified quite a bit for handling the special case of Chebyshev fitting. See this for instance. $\endgroup$ – J. M. is a poor mathematician Aug 4 '11 at 16:41
  • $\begingroup$ @MikeSpivey My understanding is that the variables $r, \alpha$ and $\beta$ have to be non-negative. But that would mean that we are restricting the solution to lines of positive slope. Should we not have to replace $\beta$ with $v_1 - v_2$ where $v_1, v_2 \ge 0$? Could you clarify? Thanks. $\endgroup$ – user137481 Nov 17 '18 at 3:16
  • $\begingroup$ @user137481: No, $\alpha$ and $\beta$ can be negative, and there's nothing in the formulation that assumes otherwise. For some data sets, sure, $\alpha$ and $\beta$ will turn out to be nonnegative, but in general you can't make that assumption. As far as $r$, yes, it must be nonnegative. However, the constraints already in the model force that, and so you don't have to include it as a separate constraint. $\endgroup$ – Mike Spivey Dec 13 '18 at 22:15
  • $\begingroup$ @MikeSpivey Thank you for the clarification. $\endgroup$ – user137481 Dec 20 '18 at 2:14

The minimization with respect to $\alpha$ is easy: Given $\beta$, we can form $\delta_i:=y_i-\beta x_i$; then the optimal value of $\alpha$ is halfway between the maximal and minimal values of $\delta_i$, and the corresponding value of $P$ is half the distance between the two. Let $i_>$ be an index (depending on $\beta$) for which the maximal value of $\delta_i$ is attained, and let $i_<$ be an index for which the minimal value of $\delta_i$ is attained; then

$$ \begin{eqnarray} \min_\alpha P(\alpha,\beta)&=&\frac{1}{2}(\delta_{i_>}-\delta_{i_<})\\ &=&\frac{1}{2}((y_{i_>}-\beta x_{i_>})-(y_{i_<}-\beta x_{i_<}))\\ &=&\frac{1}{2}((y_{i_>}-y_{i_<})-\beta(x_{i_>}-x_{i_<}))\;. \end{eqnarray} $$

Now assume that for a given $\beta$ there is only one index each for which the maximal and minimal values of $\delta_i$ are attained. Then in some sufficiently small neighbourhood of that value of $\beta$ these indices will not change as we vary $\beta$. That means we can decrease $\min_\alpha P(\alpha,\beta)$ by changing $\beta$ in the direction of the sign of $x_{i_>}-x_{i_<}$. Thus, such a value of $\beta$ cannot be the optimal one; that is, the optimal $\beta$ is one for which either the minimal or the maximal value of $\delta_i$ is attained for two different indices. In other words, the optimal $\beta$ is such that some line in the convex hull of the points $(x_i,y_i)$ has slope $\beta$.

Now as we increase $\beta$, $i_<$ increases from $1$ to $n$ and $i_>$ decreases from $n$ to $1$; the value of $\min_\alpha P(\alpha,\beta)$ decreases as these indices move towards each other and then increases again after they've passed each other. The optimal $\beta$ is one where one index for which $\delta_i$ is minimal lies between two indices for which $\delta_i$ is maximal, or vice versa. If the points are in general position, there will be a unique value of $\beta$ with this property.

[Edit:] I just noticed that in the last paragraph I assumed that the points are ordered with increasing $x_i$, but you hadn't assumed that. If they aren't ordered, replace "$i_\lt$ increases" by "$x_\lt$ increases" and "$i_\gt$ decreases" by "$x_\gt$ decreases".

  • $\begingroup$ I am still a bit confused about your approach. So what is this approach called? $\endgroup$ – Fan Zhang Jun 27 '11 at 15:05
  • $\begingroup$ @Fan: I don't know that it's called anything -- I made it up in response to your question :-) What part are you confused about? $\endgroup$ – joriki Jun 27 '11 at 17:45

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.