Take the 2-minute tour ×
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.

So, I'm playing a game where there is a certain percent value that changes over time. I look at it occasionally, it seems to be approximately linear in time. However, the change is slow enough that I want something better than simple linear regression.


$f(x) := ax+b$

$g(x) := \mathrm{round}(f(x))$

Given pairs $\{(x_1,g(x_1)),\dots,(x_n,g(x_n))\}$, estimate $a$ and $b$.

share|improve this question
Could you be more specific with the "messed up too much"? What exactly happens if you regress over $(x_i,g(x_i))$ values? –  Guess who it is. Dec 4 '10 at 6:58
I suppose I just mean I want something more accurate than that. (editing question now) –  Ricky Demer Dec 4 '10 at 7:38
Well, if you don't know what the true values $f$ are, it's a bit disingenuous to talk about "accuracy". :) –  Guess who it is. Dec 4 '10 at 7:41
unless there are too many data points to practically find as exact of a solution as is possible. –  Ricky Demer Dec 4 '10 at 7:59

1 Answer 1

up vote 1 down vote accepted

Given pairs $(x_i,y_i)$, you can try to find $a,b$ that minimize the $L^\infty$ distance from $y_i$ to $ax_i+b$ using LP, which is $\max_i |y_i-ax_i-b|$; if $y_i$ indeed depends linearly on $x_i$ up to rounding, then there's a choice of $a,b$ with $L^\infty$ distance of less than $1/2$.

There may be a simpler way to solve this particular optimization problem, but an LP would work, especially with your small dataset. But if your model is wrong, you might get garbage because of the unforgiving $L^\infty$ metric. Minimizing the $L^1$ metric can also be formulated as an LP, and minimizing the $L^2$ metric is the well-known least-min-squares, for which there is an explicit solution.

share|improve this answer
This details an algorithm for doing Yuval's suggestion. Remember though: "garbage in, garbage out". –  Guess who it is. Dec 4 '10 at 8:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.