I am struggling to solve a least square problem in which the tedious part is the initialization. Grid search methods are out of question.
The initial problem
I've stated my problem in a previous question Can I find a closed form solution for this system of equation?, still unsolved.
To summarize the problem, I'm trying to estimate the parameters $(x_0,y_0,v_x,v_y)$ of the model $$ M(t)=\frac{v_x(x_0+tv_x+a)+v_y(y_0+v_yt)}{\sqrt{(x_0+v_xt+a)^2+(y_0+v_yt)^2}}+ \frac{v_x(x_0+tv_x-a)+v_y(y_0+v_yt)}{\sqrt{(x_0+v_xt-a)^2+(y_0+v_yt)^2}} \tag1$$
$M(t)$ for $t=t_1,t_2,...,t_n$ is the known input and $(x_0,y_0,v_x,v_y)$ is the looked-for output. $a$ is a known constant.
$M(t)$ is the measurment available. The least square cost function has a lot of local minima and I can't figure out a good initialization.
How I recast it
We can also write the model as, with 5 parameters $\left(v,t_{cpa}^{(1)},t_{cpa}^{(2)},d_{cpa}^{(1)},d_{cpa}^{(2)}\right)$: $$ M(t)=\frac{v^2\frac{t-t_{cpa}^{(1)}}{d_{cpa}^{(1)}}}{\sqrt{1+\left(v\frac{t-t_{cpa}^{(1)}}{d_{cpa}^{(1)}}\right)^2}}+\frac{v^2\frac{t-t_{cpa}^{(2)}}{d_{cpa}^{(2)}}}{\sqrt{1+\left(v\frac{t-t_{cpa}^{(2)}}{d_{cpa}^{(2)}}\right)^2}}\tag2 $$
To find the intial 4-parameters set from this 5-parameters set, we'll need additional constraints which arn't stated here.
In $(2)$ I write $x=v\frac{t-t_{cpa}^{(1)}}{d_{cpa}^{(1)}}$ and $y=v\frac{t-t_{cpa}^{(2)}}{d_{cpa}^{(2)}}$, then assuming I can find $v$ (which isn't a strong assumption in my case), $(2)$ is rewritable as :
$$ \frac{M(t)}{v}=\frac{x\sqrt{1+y^2}+y\sqrt{1+x^2}}{(1+x^2)(1+y^2)}\tag3 $$
The final problem
Squaring $(3)$ two times we can get rid of the square roots, and we end up with a 8-th order polynomial in $t$, however, please note that $M(t)$ may be negative or positive. I'm thinking about determining the coeficients of the polynomials using a polynomial regression.
So my final question is :
1- Can I find numericaly, in a (relatively, recall I'm just looking for an initialization strategy) robust and quick manner, ALL the solutions of a system of univariate polynomials ? if yes, how can I proceed in an efficient way ?
2- If I add the previously mentioned constraint on my 5-parameters set, such that the least square solution may be the right one, will I be bothered by the fact that I squared my model two time ? Is the closed form solution form the least square minimization robust in the case of a system of 8-th order polynomials ? Adding some constraint, do the closed form solution for polynimals regression still hold ? Will I be bothered with initialization problem if I go for gradient descent ? How stable are polynomials regression problem ? Considering the system is univariate, can I go with gaussian elimination, if yes, is there a way to do it with poor skill with formal math tools ?
That's a lot of questions, but I can't spend too much time invasting all this issues, so even any partial response that give me some insight is greatly welcomed.
Univariate polynomials of degree $8$ do not have closed-form solutions. The numerical determination of the roots is trivial, special attention has to be paid to the case of multiple roots since they greatly amplify floating point errors.
A system of $n$ polynomial equations in $n$ variables of degree $d$ can have up to $d^n$ solutions. The complexity of finding all solutions is dominated by this quantity as a factor, even if a noticeable number of the solutions is at or close to infinity (i.e., the do not exist except in a projective reinterpretation of the system).
Polynomial regression for the coefficients of an otherwise unstructured polynomial of degree $8$ requires at least $9$ samples. Regression works best if there are more samples that are spread out over a large interval. The number of samples and the interval covered influence the stability.