Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
How are $d_i$ defined exactly, or are they just constants? –  Hauke Strasdat Oct 13 '12 at 12:38
    
@HaukeStrasdat Values of $d_i$ are arbitrary positive constants, not necessarilly equal. –  user506901 Oct 13 '12 at 12:53
1  
In the general case, there will usually be many local minimas. If you simply start at some point and "follow" the gradiant, chances are high that you will end at some local minimum, not the global one. –  fgp Oct 13 '12 at 13:02
    
Hm, the first thing which comes to my mind is that $g_i(x_n) := (d_i-||x_i-x_n||)^2$ does not approximate zero at the minimum $(x_n,f(x_n))$ since $d_i$ are arbitrary. So it is strictly speaking not a least-squares problem and thus the Gauss-Newton method is no applicable, AFAIK. Did you try another iterative method such as gradient descent or the Newton method? –  Hauke Strasdat Oct 13 '12 at 13:04
    
@HaukeStrasdat Well, the point is that iterative methods such as gradient descent is often used. But, why can't one just set the derivative of $f(x_n)$ wrt $x_n$ to zero, and solve for $x_n$? –  user506901 Oct 13 '12 at 13:08
show 4 more comments

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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