Least squares minimization of point distances (nonlinear)

Question

We have two sets of 2D points $\bar{x}\leftrightarrow \bar{x}'$ (the bar denotes a vector, i.e. $\bar{x}=(x,y)^{T}$). I would like to minimize discrepancy between the points using the least squares objective function:

$$e=\frac{1}{2}\sum_{i}\left(P\bar{x}_{i}-\bar{x}'_{i}\right)^{2}$$

We would like to find best parameters of $P$ by taking partial derivatives of $e$, which means effectively taking derivatives of $P$.

The $P$ consists of scaling followed by rotation and has two parameters:

$$P(\theta,s)=R(\theta)S(s)=\begin{pmatrix}cos(\theta) & -sin(\theta) \\ sin(\theta) & cos(\theta)\end{pmatrix}\begin{pmatrix}s & 0 \\ 0 & s\end{pmatrix}$$

Finding partial derivatives with respect to $\theta$ or $s$ is easy via the product rule:

$$\begin{align}\frac{\partial}{\partial \theta}P &=\frac{\partial R}{\partial \theta}\cdot S\\ \frac{\partial}{\partial s}P &=R\cdot \frac{\partial S}{\partial s}=R\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}\end{align}$$

This would be all that is needed to start some numerical optimization (it is obviously nonlinear least-squares due to rotation). Anyway, what if we need an extra term in $P$, like this:

$$L(\mathbb{x}|k)=\begin{pmatrix}x^{2}k \\ xyk\end{pmatrix}$$

with

$$P_{new}(\theta,s,k)=L_{k}\left[ R(\theta)S(s) \right]$$

To find derivatives at $\bar{x}$, I suppose we have to use chain rule, e.g.

$$\frac{\partial}{\partial\theta}P_{new}(\bar{x})=\frac{\partial}{\partial\theta}(L\circ RS\bar{x})=\frac{\partial}{\partial\theta}L\left(RS\bar{x}\right)=\frac{\partial L}{\partial RS\bar{x}}\cdot\frac{\partial RS\bar{x}}{\partial \theta}$$

Since $L$ is also function of a 2-vector, its derivative is a Jacobian:

$$\frac{\partial{L}}{\partial\bar{v}}=\begin{pmatrix} 2v_{1}k & 0 \\ v_{2}k & v_{1}k \end{pmatrix}$$

I suppose the vector $RS\bar{x}$ should be substituted into that matrix to compute the derivative analytically for the given $\bar{x}$.

I have done the computation but it does not work. The partial derivatives are different from what has been computed explicitly.

Answer 1

I consider the first part of your post ; I do not understand one word of the second part. If I understand correctly your question, then you search the minimum of $f(s,\theta)=\sum_i||P\bar{x_i}-\bar{x'_i}||^2$. It suffices to solve the following system of $2$ equations in the unknowns $s,\theta$:

$1/2\dfrac{\partial f}{\partial s}=\sum_i (P\bar{x_i}-\bar{x'_i})^T(\dfrac{\partial P}{\partial s}\bar{x_i})=0$ and $1/2\dfrac{\partial f}{\partial \theta}=\sum_i (P\bar{x_i}-\bar{x'_i})^T(\dfrac{\partial P}{\partial \theta}\bar{x_i})=0$ where $\dfrac{\partial P}{\partial s}=\begin{pmatrix}\cos(\theta)&-\sin(\theta)\\\sin(\theta)&\cos(\theta)\end{pmatrix}$ and $\dfrac{\partial P}{\partial \theta}=\begin{pmatrix}-s\sin(\theta)&-s\cos(\theta)\\s\cos(\theta)&-s\sin(\theta)\end{pmatrix}$.

Answer 2

Let $A$ represent the original points, i.e. the $k$th column of $A$ is $x_k$. And let $B$ the represent primed points. Then the function to be minimized is $$f=\frac {1} {2} \|PA-B\|^2_F$$

This problem is closely related to the Orthogonal Procrustes problem, with a scaling matrix thrown into the mix.

The solution to the standard OP problem is to take the Singular Value Decomposition of $BA^T = UDV^T$ and replace the $D$ matrix by the identity, yielding $P=UV^T$ as the solution.

However, to accomodate scaling, replace $D$ with a scalar multiple of the identity, so that $P = sUV^T$.  Finally, the value of $s$ which minimizes $\|sUV^TA-B\|^2_F$ is $s = \frac {{\rm tr}(D)} {{\rm tr}(A^TA)}$.

So there is a closed-form solution to the first part of your question, no need for numerical optimization.

As for the second part of your question, I don't understand what you're asking.