I am trying to do linear regression on the following conceptualized problem. I have a set of data in pairs $(x, y)$. I know that $y$ is bounded by a linear function $f(x) = mx + c$. I want to estimate this upper bound. Following are visualization of the data generated for two values of a third parameter.

enter image description here

enter image description here

As you can see applying linear regression blindly would not help. How can I get around this problem?

  • 2
    $\begingroup$ The question to ask is what "best line" means. $\endgroup$ Mar 5 at 23:25

1 Answer 1


We can formulate the task of finding a straight line bounding the cloud of data points as constructing a straight line that touches the data set at least at two points, and the rest of the data points are either on the straight line or below it. In other words, we want to find two coefficients $m,c$ such that for all data points $(x_i,y_i)$ it holds $y_i \leq m x_i + c$ and for at least two data points it holds $y_i = m x_i + c$.

Such a solution can always be found but in general the answer is not unique. Without writing a rigorous proof of this, let's just illustrate it pictorially using the cartoon here.

First let's find the maximum data point in the data set $P_0$ corresponding to some $(x_{0},y_{0})$, where $y_0 \geq y_i$ for all $i$. If there is more that one data point with $y=y_{0}$ then the function $y=y_{0}$ satisfies our definition of the bounding linear function. If there is only one data point with $y=y_{0}$ then we'll first construct a straight line $y=y_{0}$ and then tilt it by some angle $\alpha$ so that it touches the next data point $P_1$. The function $y = y_0 + (x-x_0)(y_1-y_0)/(x_1-x_0)$ defining the straight line $(P_0,P_1)$ satisfies our definition of the bounding linear function.

However, in general one can find another bounding line $(P_0,P_2)$ by using the tilt in the opposite direction. Furthermore, in general one can construct bounding straight lines that don't contain the maximum point $P_0$. To see that, construct the smallest convex polygon containing the data set (the shaded area) and observe that some of the edges of the polygon can serve as bounding straight lines for the data set, e.g., line $(P_2,P_3)$ in the cartoon. enter image description here


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.