# Advice to solve a system of 8th order univariate polynomials

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.

• From your other post I take it that the input is $t_k,\,k=1,..,N$ and $M(t_k)$ and the searched-for output is $x,y,v_x,v_y$? And $a$ might be both? How do you arrive at the idea that solving for $t$ might accomplish something useful? – Dr. Lutz Lehmann Mar 18 '15 at 16:14
• I've eddited the question according to the ambiguous points. I indeed know $M(t_k)$ and $a$ and I'm looking for $(x_0,y_0,v_x,v_y)$. In a latter part of my post I use $x$ and $y$ as notations and it is unrelated with $x_0$, $y_0$. I do not want to solve for $t$ but find the coeficients of the 8-th order polynomials using a polynomial regression and then use the coefficient's values to infer the looked-for parameters. Polynomial regression admit a closed form solution, but I don't know to much thing about it. Please excuse me if I'm hard to understand, my english isn't so good. – Antoine Bassoul Mar 18 '15 at 16:25
• @AntoineBassoul: I would like to help, but the presentation is very confusing. For $(2)$, what are the unknowns and how do we generate the system of equations? The recasted form is promising but an advice: kindly get rid of the superscripts and subscripts for $t^{(1)}_{cpa}$, and to prevent ambiguity, explicitly write down the recasted system of $n$ equations in $n$ unknowns as just $x_1, x_2, x_3,\dots, x_n$. (Your other question was much clearer. Pls present this question in the same way.) – Tito Piezas III Mar 19 '15 at 3:29

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.