How to apply Gradient Descent to a summ of function

Question

My target is to find a center of a circle that approximate a set of dots

i want to find minimum of a function: $$\sum_{i=0}^N (\sqrt{(x_i - a)^2 + (y_i - b)^2} - R)^2$$

this function represent an error of a my approximation of a set a dots on a plane with a circle.

I did a bit of a googling and find that Gradient Descent is a decent method for a numerical searching for a minimum of function.

But i have a trouble with understanding how i should correcnt my A,B,R with partial derrivative, when i have function of summ.

picture related for better explanation of my problem: https://i.stack.imgur.com/vSsZU.jpg

Maybe this is banal, but: what about a simple average of the dots coordinates to find the circle center, and the average distance from that center to the dots to have the radius? — Vincenzo Lavorini, Jun 21, 2018 at 14:51
there is potentially a much noisy dots with spikes, so it's probably not the best option. — stronk_kisik, Jun 21, 2018 at 15:16
But if the source data is noisy, then the surface where you want your gradient to descent is also filled with local minima, and your gradient can fall down into one of those, missing the global minimum. So a simple solution like this is also much more robust: you are guaranteed to catch the global minima. And if you want to exclude outliers, you can use a two step process: extract circle center and radius in the way I suggested, excluding the dots too far from the radius, repeat the first step to extract the new center and radius. — Vincenzo Lavorini, Jun 21, 2018 at 15:31
@VincenzoLavorini , averaging doesn't work well for circle with skipped sector. I use averaged x,y coordinates and estimated radius as seed value for algorithm and it works good now. — stronk_kisik, Jun 26, 2018 at 12:01

stronk_kisik · Accepted Answer · 2018-06-26 12:09:09Z

0

I came up with the simple answer after I just rewrite this idea on paper:

$$\frac{\delta \sum \Big[f(x,y)\Big]}{\delta x} = \sum \frac{\delta f(x,y)}{\delta x}$$

so it's just partial derivative for each Experimental Dot summed. Algo works quite well.

answered Jun 26, 2018 at 12:09

stronk_kisik

293 bronze badges

$\begingroup$ Hey, the question is great. What does it mean when you say "experimental dot" summed? I am not familiar with this concept. $\endgroup$
– akshit bhatia
Mar 4, 2020 at 23:58

Add a comment |

1 Answer 1