Sign up ×

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|cite|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? – J. M. 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". :) – J. M. 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|cite|improve this answer
This details an algorithm for doing Yuval's suggestion. Remember though: "garbage in, garbage out". – J. M. Dec 4 '10 at 8:02

Your Answer

