I just learned about the Gauss-Newton method in Uni and was programming something where I wanted to apply this. I got a program and want to find the runtime-coefficient. Basically I know that my runtime $f$ is proportional to the number of inputs($n$) that it processes(to some power)
$$t(n) = a\cdot n^b$$
Now, I ran my program and got $m$ different $t(n)$ values (for different $n$) to optimize my parameters $(a,b)$.
I set up my matrices the following way:
$$x := (a,b)$$ $$f(x) = \begin{bmatrix} a\cdot n_1^b - t_1\\ a\cdot n_2^b - t_2\\ a\cdot n_3^b - t_3\\ ...\\ a\cdot n_M^b - t_M \end{bmatrix}$$
$$Jf(x) = \begin{bmatrix} n_1^b & a\cdot n_1^b \cdot ln(x) \\ n_2^b & a\cdot n_2^b \cdot ln(x)\\ n_3^b & a\cdot n_3^b \cdot ln(x)\\ ...\\ n_M^b & a\cdot n_M^b \cdot ln(x) \end{bmatrix}$$
The Gauss-Newton method did not converge for this (assuming that my implementation is correct). I even deleted the parameter a and created some data which fits the function $t(n) = n^{1.5}$ I started with $b=1.4999$ and it did not converge aswell. So I am slightly confused my this does not work.
Disregarding the Gauss-Newton method, how could I calculate my coefficients $a$ and $b$ otherwise? How is it usually done?
If I may suggest, be careful with this kind of problems.
In the least square sense, you want to minimize $$SSQ_1=\sum_{n=1}^p \big(a x_n^b-t_n\big)^2$$ The model is nonlinear (because of $b$) and then, as usual, you need starting guesses for the parameters.
One way to get them is linearization, as Jair Taylor answered. This corresponds to the minimization of $$SSQ_2=\sum_{n=1}^p \big((c + b \log(x_n)-\log(t_n)\big)^2 \qquad\text{where}\qquad c=\log(a)$$ and this is just a linear regression (easy to do).
Now, the problem is that what is measured is $t$ and not any of its possible transforms. Then, if you want to be strict, you need nonlinear regression which will converge quite fast because the first step did provide at least reasonable estimates.
If you do not access a software for nonlinear regression or if you want to make your own, the problem can easily be set. Using the partial derivatives (to be set equal to $0$), we have $$\frac{\partial SSQ_1 } { \partial a}=2 \sum_{n=1}^p x_n^b\big(a x_n^b-t_n \big)\tag1$$ $$\frac{\partial SSQ_1 } { \partial b}=2a \sum_{n=1}^p x_n^b\log(x_n)\big(a x_n^b-t_n \big)\tag2$$
From $(1)$,we can express $a$ as a function of $b$ $$a=\frac{\sum_{n=1}^p x_n^b t_n}{\sum_{n=1}^p x_n^{2b}}$$ Plug in $(2)$, reduce to same denominator to end with an equation in $b$ and you want to find the zero of it.
This would be very simple to do using Newton method with numerical derivatives (to make life easier).