0

I have a hidden linear function: $f(x)=a*x+b$. For example $f(x)=2*x+3$

A hidden function $f$ was executed on some hidden input $x$=(0,1,3,4) and we have access only to output $y=(f(0)=3, f(1)=5, ...)=(3,5,9,13)$

How to find: $(a, b, \vec{x})$? In this case the correct answer is $(a=2, b=3, x=(0,1,3,4))$

There is possibility to construct the system of equations but I do not know how to solve them. $$\begin{cases} a*x_1+b=3,\\ a*x_2+b=5,\\ a*x_3+b=9,\\ a*x_4+b=13.\\ \end{cases}$$ The number of unknowns is greater than knowns, but we are limited to linear hidden functions only. Should I rewrite as matrix multiplication and use some sort of decomposition? Should I use Linear programming?

Note: there exists trivial solution $(a=1, b=0, x=y)$ I am interested in non trivial solutions and general approach for any $(a,b,x)$

Edit1: what are the possible restrictions to get unique solution? For example: $(a,b,x)$ natural numbers, maximize $(a, b)$ and minimise $(x)$,...

Oleg Dats
  • 425
  • 1
    If you don't know $a$ and $b$, indeed the number of unknowns is greater than the number of equations and you can basically choose any solution that you want. You can for example always fix $a=1$ and $b=0$, which always gives you a trivial solution. Or do you have some restrictions for the relationships between $x_1, x_2 $ etc? – Matti P. May 12 '21 at 10:54
  • @MattiP. thank you for a nice comment. I am not interested in trivial solutions. I will update the question. – Oleg Dats May 12 '21 at 10:55
  • 1
    This question is missing some necessary information. What are $3,5,9,13$? I see that if $f(3)=9$ and $f(5)=13$, then $(a,b)=(2,3)$. But I'm just guessing here! And where does $(0,1,3,4)$ come from? Please tell us the whole story. – TonyK May 12 '21 at 10:57
  • That's better! Now it makes sense. – TonyK May 12 '21 at 11:15

2 Answers2

1

There are infinitely many solutions. If $a \ne 0$, then we can always fix $(a,b)$ and then solve for $x_i$.

Assuming you are looking for non-negative integer solutions.

If $a=1$, then we can set $b \in \{1,2,3\}$ and then decide for $x_i$.

Now assume $a>1$,

$$a(x_2-x_1)=2$$

$$a(x_3-x_1)=6$$

$a$ is a common divisor of $2$ and $6$. $a=2$ and we can either pick $b$ to be $1$ or $3$ and then solve for corresponding $x_i$.

Possible restriction: Let $b$ to be as large as possible and all variables are nonnegative.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Is it possible to prove that following this approach and having this restriction we get unique solution? – Oleg Dats May 12 '21 at 16:55
  • 1
    with nonnegtive constraint and if we want to maximize $b$, then $b$ must take value $3$. Clearly $a \ne 0$, hence $x_1=0$. At this point it is still not unique. If we further impose the condition that $a>1$, then the solution is unique. – Siong Thye Goh May 13 '21 at 03:04
1

The question, as originally posted, is unsolvable uniquely. You can imagine that easily, this way: Suppose we try plotting $f(x)$ on the Cartesian plane. We have access to $4$ outputs, so we draw the lines: $$y=3$$ $$y=5$$ $$y=9$$ $$y=13$$ We know that our function must intersect all $4$ lines. Now you can see the problem very clearly. Any line with a non-zero slope will certainly intersect all $4$ lines. So this much information is not enough to solve the question. Even if we were given the value of a, that is, the slope of the line, still we could create infinite parallel lines which would satisfy the given conditions. So it would still be unsolvable.

Ritam_Dasgupta
  • 5,992
  • 2
  • 8
  • 23
  • I see. Can you please suggest: what are the possible restrictions get unique solution? For example smallest non-negative integers... – Oleg Dats May 12 '21 at 11:29
  • 1
    That could be a possible restriction. But which variable do we want to be the smallest? I mean, the there are basically 6 unknowns to be found out. So on the set of real numbers solution can't be found without 6 equations. But if you look for solutions in some other set, say, natural numbers or integers, it could possibly be done. – Ritam_Dasgupta May 12 '21 at 11:52
  • For example: $(a,b,x)$ natural numbers, maximize $(a, b)$ and minimise $(x)$. Is it possible to find unique solution then? – Oleg Dats May 12 '21 at 13:23