0
$\begingroup$

Suppose a set of $n-1$ are given in 2D space, $x_1, x_2, \dots, x_{n-1}$, and an additional point $x_n$ is to be assigned a 2D coordinate such that the prescribed Euclidean distances $d_1, d_2, \dots, d_{n-1}$ of this points to points $x_1, x_2, \dots, x_{n-1}$ are matched as best as possible in least-squares sense.

In other words, a function to be optimized is: $f(x_n)=\sum_{i=1}^{n-1} (d_i-\|x_i-x_n\|)^2,$ is minimized. An approach to achieve the minimimum is to adapt some form of iterative minimizers (at least in the literature I have on disposal). However, an approach to minimize the function is to find its derivative wrt $x_n$, set it to zero,$\frac{\partial}{\partial x_n}f(x_n)=0,$ and solve for $x_n$. Why is such approach not applicable here? Is is due to hardness of finding a derivative (or impossibility to find one), or due to computational effort?

  • 0
    @hardmath So, the argument is that the derivative cannot be found, and therefore one has to adopt, eg, gradient descend?2012-10-13

1 Answers 1

0

Let's write the parameters $y = (u,v)$ and the function to be minimized as:

$f(y) = \sum_{i=1}^{n-1} (d_i-\|x_i-y\|)^2 $

Since $f(y)$ tends to $+\infty$ uniformly as $y$ recedes from the origin, this continuous function does attain a global minimum, and the general theory tells the minimum is attained at a critical point (since no boundary is involved), i.e. at a point where either the first partial derivatives are all zero or some are undefined.

This problem is nonetheless much harder than a linear least squares fitting problem because the latter ordinarily has a unique critical point where partials vanish which can be determined by solving a linear system.

There are multiple critical points of the "undefined derivative" kind, as pointed out in the comments. These at least are known a priori as $y = x_i$, since elsewhere the first partial derivatives $\partial f/\partial u, \partial f/\partial v$ are defined and bounded.

Further consider finding critical points where first partials vanish simultaneously using this formula:

$ \partial f/\partial u = 2 \sum_{i=1}^{n-1} (\|x_i-y\| - d_i) \frac{(u - x_i^{(1)})}{\|x_i - y \|} $

and the corresponding expression for $\partial f/\partial v$. Since $u,v$ appear in the denominator via $y$ and and inside a radical courtesy of the norm of $x_i - y$, a pair of such simultaneous equations (setting the first partials to zero) will be quite nonlinear.