# Exponential extrapolation

Given a set of points on 2D surface $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$ and a function $f(x)=k+ab^x$, the task is to find values of $k,a$ and $b$ that minimize the following sum:

$$\sum_{i=1}^n (k+ab^{x_i}-y_i)^2.$$

I tried to get derivatives (with respect to $k,a,b$) from this sum and got the system of three equations, but it's impossible for me to express unknowns from it. Also I'm looking for numerical answer.

Does anyone know how to do that? Thanks for the help.

-
It would help the readers if you posted the system of equations -- in fact, your problem might even have been errors in computing the system, and posting it would let us see. – Hurkyl Apr 6 '13 at 11:46
Are you in a setting that expects a symbolic answer? Or are you in a setting where a numeric answer is sufficient? While I imagine it should be easy to eliminate $k$ and $a$ (aren't the equations linear in those variables?), just eyeballing the equation makes it look like you'll need a numeric solution for $k$ (Or familiarity with LambertW, I suppose). And even if a symbolic solution is possible, a numeric one might be easier. – Hurkyl Apr 6 '13 at 11:50
Did you try rewrite a equation like $\ln(y_i - k) = \ln a + x \ln b$? You can use simple regression in this case. – Orat Apr 6 '13 at 11:53
I haven't noticed $k$ is also variable... But that transformation may help. – Orat Apr 6 '13 at 11:55
If a numeric answer is fine, my first thought would be to try Newton's algorithm. Or simply use a binary search or plot the function and pick it out visually, depending on which one is easier to implement. – Hurkyl Apr 6 '13 at 12:04

Gauss-Newton algorithm directly deals with this type of problems. Given m data points $(x_i,y_i)$ for regression with a function of n parameters $\vec \beta =(\beta_1,...,\beta_n)$ $$min_{\vec \beta }\ S(\vec \beta)\ where\ S(\vec \beta)=\sum_{i=1}^m r_i(\vec \beta)^2=(y_i-f(\vec \beta,x_i))^2$$ I skip the derivation of algorithm which you can find in every textbook (First use Taylor approximation and then use Newton's method). $$\Delta \vec \beta=\big(J^T\ J\big)^{-1}\ J^T\ \vec r$$ $$\vec \beta=\vec \beta + \alpha\ \Delta \beta$$ where $\alpha$ is damping coefficient and $$J=\begin{pmatrix}\bigg(\frac{\partial f}{\partial \beta_1}\bigg)_{x=x_1}&...&\bigg(\frac{\partial f}{\partial \beta_n}\bigg)_{x=x_1}\\\ ...&...&...\\\ \bigg(\frac{\partial f}{\partial \beta_1}\bigg)_{x=x_m}&...&\bigg(\frac{\partial f}{\partial \beta_n}\bigg)_{x=x_m}\end{pmatrix}\quad \vec r=\begin{pmatrix}y_1-f(\vec \beta,x_1)\\\ ... \\\ y_m-f(\vec \beta,x_m) \end{pmatrix}$$ For your specific case $$\frac{\partial f}{\partial a}=b^{x_i}$$ $$\frac{\partial f}{\partial b}=a\ b^{x_i-1}\ x_i$$ $$\frac{\partial f}{\partial k}=1$$

-
Thanks for the answer (+1), but I solved it in a different way (see my answer). – ArtemStorozhuk Apr 6 '13 at 14:22
@ArtemStorozhuk you welcome. Thanks for notification – Occupy Gezi Apr 6 '13 at 14:46

If you don't want to have to think too much, you can chuck your problem into some Gauss-Newton or Levenberg-Marquardt routine and be done with it. If you're willing to do a bit of analytical work, here's a way that might make for a less computationally-intensive solution.

You can ease your problem by recognizing that your model is linear in the parameters $a$ and $k$. In particular, taking partial derivatives of your objective function with respect to those two parameters and equating to zero results in the following set of linear equations:

$$\begin{pmatrix}\sum_j^n b^{2x_j}&\sum_j^n b^{x_j}\\\sum_j^n b^{x_j}&n\end{pmatrix}\begin{pmatrix}a\\k\end{pmatrix}=\begin{pmatrix}\sum_j^n y_j b^{x_j}\\\sum_j^n y_j\end{pmatrix}$$

which is easily solved with Gaussian elimination or Cramer's rule.

Now, taking the partial derivative with respect to the nonlinear parameter $b$ and equating to $0$ gives

$$\sum_j^n \left(x_j b^{x_j}\left(a b^{x_j}+k-y_j\right)\right)=0$$

Substituting the values of $a$ and $k$ obtained from the linear equations now yields a nonlinear equation in the single unknown $b$, which can then be solved with the standard methods like Newton-Raphson or Brent. Of course, you need a good guess for $b$; that's the part of the problem you will need to reckon out for yourself. Once you've obtained a nice value for $b$, you can then substitute it into your explicit expressions for $a$ and $k$.

-
Thanks for the answer (+1), but I solved it in a different way (see my answer). – ArtemStorozhuk Apr 6 '13 at 14:22

I used @Taro hint to solve this task.

$$\ A=lna\\ B=lnb$$

And rewritten the function: $$\ ln(y_i-k)=A+x_iB$$

After this I've got a system with 2 unknowns $A$ and $B$ ($k$ is parameter):

$$\begin{cases} \sum_{i=1}^n ln(y_i-k)=nA+B\sum_{i=1}^nx_i \\ \sum_{i=1}^n ln(y_i-k)x_i=A\sum_{i=1}^nx_i+B\sum_{i=1}^nx_i^2 \end{cases}$$

As you can see right part of system is static - only left part depends on $k$.

And solved it with binary search (used $k$ as parameter).

Here's a result:

-