2
$\begingroup$

I have a dataset, that only takes integer values ($x$ and $y$ coordiantes). E.g. my data is the following: $x = (1,2,2,3,3), y = (1,2,3,3,4)$. I want to make a linear regression through the data, i.e. $y = -0.07+1.21x$. However this function doesn't make sense, as the values are not integers. So instead I rather want an integer valued "linear" function, that best approximates the data. That is I want a function of the form: $$f(x) = [m\cdot x+q]$$ Where $[\cdot ]$ is the nearest integer function. Of all these functions I want [the] one that minimizes $r^2 = \sum_i \left(y_i -f(x_i)\right)^2$

In my dataset $f(x) = [x]$ would be an optimal solution. However the underlying linear function is not unique, e.g. $f(x) = [x+0.1]$ will do equally good. Furthermore the function $f(x) = [1.4x]$ which is indeed different has the same $r^2$.

Is there a (hopefully analytical) way to find one function that minimizes the residuals?

In case the solution is not unique, it would be interesting to know, but not really necessary. Note that the functions $f_1 (x) = [x]$ and $f_2(x) = [x+0.1]$ are the same, if their domain is $\mathbb{Z}$.

$\endgroup$
3
  • 1
    $\begingroup$ integer valued linear function has an unclear meaning. If indeed you seek the regression in the form of an integer part (or closest integer) of linear function, you will face (and you did), for obvious reasons, the non-uniqueness. If, on the other hand, you want an affine function with integer coefficients, the solution will be, again, potentially non-unique, but easier to find. And finally, what is your question exactly?=) $\endgroup$ Nov 8, 2017 at 12:35
  • $\begingroup$ The function doesn't have to be affine. The mathematical definition of the function ($f(x) = [m\cdot x+q]$) is the one that should be satisfied. However having only integer coefficients (as I'm only interessted in the domain $\mathbb{Z}$) also fullfills the definition automatically. Non uniqueness is not a big problem, however I doubt that there will be several solutions to my data set (changing the underlying linear fucntion doesn't really create a new solution, as the rounded function is identical on the domain $\mathbb{Z}$) $\endgroup$ Nov 8, 2017 at 14:24
  • $\begingroup$ Here is an integer non-uniqueness: $X=\{-1,0,1\}, Y=\{4,1,0\}$ You can create $(3,1,0)$ or $(4,1,-1)$ but the exact match is impossible. $\endgroup$
    – fedja
    Nov 19, 2017 at 5:39

1 Answer 1

0
$\begingroup$

As already proposed by @TZakrevskiy the solution is not unique.

I numerically found that

$$f(x) = [0.9x+b] $$

has with $0\leq b<0.6$ a total least square error of $2$.

Another solution is $$g(x) = [0.8x+b]$$

with $0.1\leq b \leq 6$ we again obtain the least square error of $2$.

By inspection, it is obvious that this value is the lowest value we can achieve, because we have two values at $x=2$ and $x=3$ that have different values (a distance of 1). This can be seen if you just try out all combinations of piecewise linear integer-valued functions that contain at least the first point. That means whatever we do we always get a least squares error of $2$ as long as we want integer values of $f(x)$.

Noting the previous fact we could also pick $f(x)=x$ and still get the same minimal error of $2$. But this function is simple and still has the same least square error of $2$ (formal determination coefficient of $R^2 \approx 0.615$; formal because the intercept is not included). Comparing this value to the Value achieved by linear least squares of $\approx 1.0714$ (determination coefficient of $R^2\approx 0.794$) seems to be acceptable.

Remark: If your data is from a dynamical experiment you could also consider to further investigate hysteresis effects which could be used to obtain a dynamical function that does contain all data values.

$\endgroup$
1
  • $\begingroup$ The data shown is of course only a small example. My data is more complex and I'm interested in a general solution how to obtain the optimal such function for any kind of data. Furthermore your two solutions ($g,f$) are "equivalent", if we restrict the domain to $\mathbb{Z}$, which is kind of a hidden assumption, because it doesn't make sense to evaluate at non integer numbers. $\endgroup$ Nov 13, 2017 at 21:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .