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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a set $S$ of coordinates $(x,y)$, and am estimating $f(x) = ax + b$ where $a > 0$. I also happen to know that $\forall x,y((x,y) \in S \implies y < f(x))$.

The question is how I can utilize this knowledge of the upper bound on values to improve the regression result?

My intuition is to run a "normal" linear regression on all coordinates in $S$ giving $g(x)$ and then construct $g'(x) = g(x) + c$, with $c$ being the lowest number such that $\forall x,y((x,y) \in S \implies y \leq g'(x))$, e.g. such that $g'(x)$ lies as high as it can whilst still touching at least point in $S$. I do, however, have absolutely no idea if this is the best way to do it, nor how to devise an algorithm that does this efficiently.

Any help would be greatly appreciated.

share|cite|improve this question
Do you know what the distribution of $y | f(x)$ is? – Jonathan Christensen Jan 25 '13 at 3:23
As Jonathan Christensen points out, the answer might depend on any assumptions about the probability distribution of $y$ given $f(x)$. Might your dataset have come about as a result of censoring? I.e. could it be that errors might be either positive or negative but you are able to observe only those data points in which the error is negative? – Michael Hardy Jan 25 '13 at 3:26
The data comes from network packets that are timestamped at the sender and the receiver, but due to network delay (which can only be positive), the sender's real time (which I'm trying to estimate here compared to the receiver's clock) will actually be a bit further along than what is in the received packet. Thus, $y$ will always be a bit lower than it should. – Jon Gjengset Jan 25 '13 at 3:42
To further answer the question, the network delay is unpredictable, but it is single-hop, so the delay ($f(x)-y$) is likely to be somewhat consistent between different values of $x$ – Jon Gjengset Jan 25 '13 at 3:45
up vote 1 down vote accepted

I played a bit with an alternative regression that used an exponential distribution for $y | \hat y$, so that $y$ has to be less than the regression line. This was motivated in part by the histogram at the bottom of page 62 of this Masters thesis, which suggests that network delay looks sort of like a shifted exponential distribution. Unfortunately, this ended badly; the maximum likelihood estimate is not always unique, and when it is unique the slope of the line does not represent the data well (it's estimated based on only two points). I'm considering writing this up and posting it to Stats.SE, because it was kind of interesting.

I think your original suggestion to do an ordinary regression and then move it up is a fine way to go about it. This is pretty easy, especially if you have a decent statistics library:

  1. Fit the regression.
  2. Calculate the residuals, the difference between the y coordinate of each point and the y coordinate of the line at that point, given by $\hat\beta_0 + \hat\beta_1 x_i$, where $x_i$ is the x coordinate of the point. There may be a built-in way to do this. There are matrix-algebra representations as well.
  3. Find the largest residual. Not largest in absolute value, just straight-up largest.
  4. Add the value of the largest residual to the intercept $\hat \beta_0$ of your regression model.

Your regression line now passes through the highest point and is above all the other points.

share|cite|improve this answer

Your Answer


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.