1
$\begingroup$

We a given measured points in $(x_i,y_i) \in \mathbb{R}^2$, $i=1,..,n$. The geometric circle fit is the circle with center (a,b) and radius $r$ that minimizes the squared Euclidean distances between the points and a circle:

$\sum_{i=1}^n (r_i-r)^2$, $r_i=\sqrt{(x_i-a)^2+(y_i-b^2)}$.

In the algorithms, we minimize $\sum_{i=1}^n (r_i-(\frac{1}{n}\sum_{j=1}^n r_j))^2$ in $a$ and $b$.

It is common to solve for $a,b$ using Gauss-Newton or Levenberg Marquardt. But the objective function is not differentiable in $(a,b)$ for all measuered points $(a,b)=(x_i,y_i)$, because the square root is not differentiable in zero. My question is: Why can we still use Gauss-Newton / Levenberg-Marquardt even though the objective function is not differentiable in some points?

Approach 1: There is a proof (Lemma 7) for the claim that measured points cannot be minima and that there cannot be minima in a small area around them (Lemma 8). I could not verify the last two lines of Lemma 7. I tried to restrict the objective function to a line through a fixed measured point $(x_l,y_l)$ and derive the first and second derivatives, but I did not get to the result stated in the proof that this restriction "(...) has a slope that changes by $-\sum_{i=1,i \neq l}^n r_i$". Is this a well known fact that other authors used as a basis in order to apply Gauss-Newton and Levenberg-Marquardt? Does someone know another source for that result or understands the argument of those last two lines?

Approach 2: It makes sense that the algorithm work well if our measured points are only small perturbations of points on a circle, so it is unlikely that a measured point is a global minimum. Anyhow, I do not see an easy explanation why the algorithms can be used without further consideration of the nondifferentiable points. If there is an explanation, I am also happy for a source.

There are several other fits with continuously differentiable objective functions, but I am particularly interested in Gauss-Newton and Levenberg-Marquardt for the geometric fit in the form described above and why we may apply them (as it has been done quite a lot).

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.