POV-Ray : Newsgroups : povray.advanced-users : Least Squares fitting Server Time
12 Jun 2024 10:44:25 EDT (-0400)
  Least Squares fitting (Message 5 to 14 of 14)  
<<< Previous 4 Messages Goto Initial 10 Messages
From: Bald Eagle
Subject: Re: Least Squares fitting
Date: 11 Mar 2023 11:30:00
Message: <web.640cab8889b6dca71f9dae3025979125@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:
> yesbird <sya### [at] gmailcom> wrote:
>
> > I can imagine following application: we have volume, constrained by low-
> > poly mesh and want to fill it with spheres with radiuses from Rmin to
> > Rmax, achieving randomized, natural-like form.
>
> Well, that of course suggests that there's an analogous spherical method.  I'll
> have to look and see...

https://arxiv.org/ftp/arxiv/papers/1506/1506.02776.pdf

I have no idea where the crazy "sphere parametrization" equations come from, but
I used _normal_ equations, and fixed a typo in the last line of code (needs
-'s), and got that to work.

Render is the test data in the table of the paper.


Post a reply to this message


Attachments:
Download 'leastsquaressphere1.png' (59 KB)

Preview of image 'leastsquaressphere1.png'
leastsquaressphere1.png


 

From: yesbird
Subject: Re: Least Squares fitting
Date: 11 Mar 2023 13:45:00
Message: <web.640ccc1289b6dca7172b976a10800fb2@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:
> https://arxiv.org/ftp/arxiv/papers/1506/1506.02776.pdf
> ...
> I have no idea where the crazy "sphere parametrization" equations come from, but
> I used _normal_ equations, and fixed a typo in the last line of code (needs
> -'s), and got that to work.

I'am afraid that this paper describes the opposite process: fitting something
_into_ sphere. I mean counctrusting arbitrary form _from_ spheres of different
radiuses to achieve best fit (most completed volume). Sorry for
misunderstanding.

Despite that, I forced this Matlab function to work, fixing a few typos.

In any case this was an interesting investigation, I suppose, we can use this
method in future for something useful.
--
YB


Post a reply to this message

From: Bald Eagle
Subject: Re: Least Squares fitting
Date: 11 Mar 2023 15:45:00
Message: <web.640ce83689b6dca71f9dae3025979125@news.povray.org>
"yesbird" <nomail@nomail> wrote:

> I'am afraid that this paper describes the opposite process: fitting something
> _into_ sphere. I mean counctrusting arbitrary form _from_ spheres of different
> radiuses to achieve best fit (most completed volume). Sorry for
> misunderstanding.

I'm not sure how you reach that conclusion, since the function takes all of the
randomly generated points and calculates the center point and radius of a single
best-fitting sphere.   It fits a sphere to the data, not the other way around.

> Despite that, I forced this Matlab function to work, fixing a few typos.

Excellent.  Maybe Matlab can process mesh vertices / point clouds too?


Post a reply to this message

From: Kenneth
Subject: Re: Least Squares fitting
Date: 11 Mar 2023 16:35:00
Message: <web.640cf37289b6dca79b4924336e066e29@news.povray.org>
That's a really nice result of fitting a set of data points to a function.  But
I wish I understood what all of this was about-- starting with the fundamental
idea of the  'sum of least SQUARES' and why 'squaring' the residual data errors
is used in these techniques.  I don't remember ever being introduced to that
concept, in either high-school or college maths classes. (But, I never took a
course in statistics.) The various internet articles on the subject that I have
read over the years are woefully complex and do not explain the *why* of it.

From the Wikipedia article "Partition of sums of squares":
"The distance from any point in a collection of data, to the mean of the data,
is the deviation. ...If all such deviations are squared, then summed, as in
[equation], this gives the "sum of squares" for these data."

The general idea of finding the AVERAGE of a set of data points is easy enough
to understand, as is finding the deviations  or 'offsets' of those points from
the average. But why is 'squaring' then used? What does that actually
accomplish? I have not yet found a simple explanation.


Post a reply to this message

From: Bald Eagle
Subject: Re: Least Squares fitting
Date: 11 Mar 2023 18:30:00
Message: <web.640d0e8689b6dca71f9dae3025979125@news.povray.org>
"Kenneth" <kdw### [at] gmailcom> wrote:
> That's a really nice result of fitting a set of data points to a function.

It's the reverse.  I'm fitting the function describing a line, circle, and
sphere to the measured data.  It's "as close to all of the data points as it can
be _simultaneously_".  And so the overall error is minimized.

> But
> I wish I understood what all of this was about-- starting with the fundamental
> idea of the  'sum of least SQUARES' and why 'squaring' the residual data errors
> is used in these techniques.

I never did much in those areas either.  And to be honest, it's "dangerous" to
be doing serious work with measured values and not understand the basics of the
statistics.  When I worked at American Cyanamid, they had a statistician come in
and give a presentation - in which he showed like 8 sets of data that all had
the same standard deviation, and all looked completely different.


> The general idea of finding the AVERAGE of a set of data points is easy enough
> to understand, as is finding the deviations  or 'offsets' of those points from
> the average.

This is an acceptable method, and of course can be found in early treatments of
computing the errors in data sets.

> But why is 'squaring' then used? What does that actually
> accomplish? I have not yet found a simple explanation.

"it makes some of the math simpler" especially when doing multiple dimension
analyses.

(the variance is equal to the expected value of the square of the distribution
minus the square of the mean of the distribution)

You're also doing a sort of Pythagorean/Euclidean distance calculation, and
that's done with squares rather than absolute values.

"Variances are additive for independent random variables"
"Say I toss a fair coin 900 times. What's the probability that the number of
heads I get is between 440 and 455 inclusive? Just find the expected number of
heads (450 ), and the variance of the number of heads (225=152
), then find the probability with a normal (or Gaussian) distribution with
expectation 450 and standard deviation 15 is between 439.5 and 455.5."

"while the absolute value function (unsquared) is continuous everywhere, its
first derivative is not (at x=0). This makes analytical optimization more
difficult"



https://stats.stackexchange.com/questions/118/why-square-the-difference-instead-of-taking-the-absolute-value-in-standar
d-devia

https://stats.stackexchange.com/questions/46019/why-squared-residuals-instead-of-absolute-residuals-in-ols-estimation




"A lot of reasons."


Post a reply to this message

From: Kenneth
Subject: Re: Least Squares fitting
Date: 11 Mar 2023 19:45:00
Message: <web.640d200189b6dca79b4924336e066e29@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:
> "Kenneth" <kdw### [at] gmailcom> wrote:
> > That's a really nice result of fitting a set of data points to a function.
>
> It's the reverse.  I'm fitting the function describing a line, circle, and
> sphere to the measured data.  It's "as close to all of the data points as
> it can be _simultaneously_".  And so the overall error is minimized.

Got it. Sorry for my reversed and lazy way of describing things.

> > The general idea of finding the AVERAGE of a set of data points is
> > easy enough to understand...
>
> This is an acceptable method, and of course can be found in early
> treatments of computing the errors in data sets.
>
> > But why is 'squaring' then used? What does that actually
> > accomplish? I have not yet found a simple explanation.
>
> "it makes some of the math simpler" especially when doing multiple dimension
> analyses.
>
> (the variance is equal to the expected value of the square of the distribution
> minus the square of the mean of the distribution)
>

So the (naive) question that I've always pondered is, would CUBING the
appropriate values-- instead of squaring them-- produce an even tighter fit
between function and data points? (Assuming that I understand anything at all
about why even 'squaring' is the accepted method, ha.) Although, I imagine that
squaring is perhaps 'good enough', and that cubing would be an unnecessary and
more complex mathematical step.

From reading at least various Wikipedia pages re: the discovery or invention of
'sum of squares' etc, it kind of gives me the impression that Gauss et al came
up with the method in an empirical way(?) rather than from any theoretical
standpoint. And that it simply proved useful.


Post a reply to this message

From: Bald Eagle
Subject: Re: Least Squares fitting
Date: 11 Mar 2023 20:15:00
Message: <web.640d267189b6dca71f9dae3025979125@news.povray.org>
"Kenneth" <kdw### [at] gmailcom> wrote:

> So the (naive) question that I've always pondered is, would CUBING the
> appropriate values-- instead of squaring them-- produce an even tighter fit
> between function and data points? (Assuming that I understand anything at all
> about why even 'squaring' is the accepted method, ha.) Although, I imagine that
> squaring is perhaps 'good enough', and that cubing would be an unnecessary and
> more complex mathematical step.
>
> From reading at least various Wikipedia pages re: the discovery or invention of
> 'sum of squares' etc, it kind of gives me the impression that Gauss et al came
> up with the method in an empirical way(?) rather than from any theoretical
> standpoint. And that it simply proved useful.

https://math.stackexchange.com/questions/63238/why-do-we-use-a-least-squares-fit


Post a reply to this message

From: Kenneth
Subject: Re: Least Squares fitting
Date: 11 Mar 2023 20:45:00
Message: <web.640d2e1589b6dca79b4924336e066e29@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:
>
> https://math.stackexchange.com/questions/63238/why-do-we-use-a-least-squares-fit
>

Those stackexchange links are proving to be fascinating and really informative;
thanks! Yes, I see now that 'squaring' has many purposes (and Pythagorean
antecedents) regarding the 'sum of squares' method. Lots to absorb!


Post a reply to this message

From: yesbird
Subject: Re: Least Squares fitting
Date: 11 Mar 2023 23:36:35
Message: <dff7ec21-4b6a-a3c5-10db-1da406397849@gmail.com>
On 11/03/2023 23:44, Bald Eagle wrote:
> "yesbird" <nomail@nomail> wrote:
> I'm not sure how you reach that conclusion, since the function takes all of the
> randomly generated points and calculates the center point and radius of a single
> best-fitting sphere.   It fits a sphere to the data, not the other way around.
Yes, exactly, but I mean something like this:
https://www2.latech.edu/~jkanno/packing.pdf

Please find fixed Matlab function in attachment.
Btw, there is a free version of ML, which supports original syntax:
https://octave.org
--
YB


Post a reply to this message


Attachments:
Download 'sphere_fit.m.txt' (1 KB) Download 'test_sf.m.txt' (1 KB)

From: Bald Eagle
Subject: Re: Least Squares fitting
Date: 16 Mar 2023 18:00:00
Message: <web.6413912d89b6dca71f9dae3025979125@news.povray.org>
"Kenneth" <kdw### [at] gmailcom> wrote:

> Those stackexchange links are proving to be fascinating and really informative;
> thanks! Yes, I see now that 'squaring' has many purposes (and Pythagorean
> antecedents) regarding the 'sum of squares' method. Lots to absorb!

Apparently, Grant has been closely monitoring our conversations, and made a
video to explain the basics:

But what is the Central Limit Theorem?

3Blue1Brown

https://www.youtube.com/watch?v=zeJD6dqJ5lo


Post a reply to this message

<<< Previous 4 Messages Goto Initial 10 Messages

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.