# Biased linear regression

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.

-
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

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.
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.
4. Add the value of the largest residual to the intercept $\hat \beta_0$ of your regression model.