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.

  • $\begingroup$ 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? $\endgroup$ – Dr. Lutz Lehmann Mar 18 '15 at 16:14
  • $\begingroup$ 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. $\endgroup$ – Antoine Bassoul Mar 18 '15 at 16:25
  • $\begingroup$ @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.) $\endgroup$ – 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.

  • $\begingroup$ I think that you havn't understood my question (or more likely I havn't been clear enough !). However, how do you find numericaly all the roots of a polynomial equation ? Can you give me a good/simple reference ? $\endgroup$ – Antoine Bassoul Mar 18 '15 at 16:46
  • $\begingroup$ The usual ranking lists have Jenkins-Traub or Laguerre in the lead. Eigenvalue decomposition of the companion matrix is also used, but is in principle the same as Jenkins-Traub. To find all solutions, deflation and root polishing are used. $\endgroup$ – Dr. Lutz Lehmann Mar 18 '15 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.