Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #16264

Re: Another little puzzle

Show key headers only | View raw

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>> A couple of further thoughts only one of which is directed at you
>>> Tim (at the end)...
>>>
>>> Given the general conception of a mean (rather than any other kind
>>> of summary statistic) as minimising the sum of squares of some
>>> "distance" metric:
>>>
>>>   Sum_{i=1,n} difference(A, t(i))^2
>>>
>>> we can characterise the two contenders by what distance is being
>>> minimised.  For the less well discussed "conventional average" (to
>>> use your terminology) we are minimising the sum of squares of the
>>> shorter arc lengths between A and the t(i).
>>>
>>> For the "vector average", we convert the t(i) to unit vectors u(i)
>>> and we calculate the mean if the u(i) to get a vector m.  The
>>> "average", A, is just the direction of this vector -- another
>>> point on the unit circle.  In this case we are minimising the sum
>>> of squares of the /chord/ lengths between A and the t(i).
>>
>> I think of this approach differently.  I take the time values
>> t(i) as being unit masses on the unit circle, and calculate the
>> center of mass.  As long as the center of mass is not the origin
>> we can project it from the origin to find a corresponding time
>> value on the unit circle (which in my case is done implicitly by
>> using atan2()).
>
> It's the [same] calculation though.

Yes, my first sentence there was meant to convey that I am
offering an alternate formulation that is mathematically
equivalent, which I expected would be self-evident.

>>> The mean vector itself (which may not lie on the unit circle)
>>> minimises the sum of the squares of the length of the vector
>>> differences m-u(i):
>>>
>>>   Sum_{i=1,n} |m - u(i)|^2
>>
>> That's true but I thought of it just as the average of the time
>> value "masses" on the unit circle.
>>
>>> and any other vector along the same line as m (i.e. c*m for real
>>> c) minimises
>>>
>>>   Sum_{i=1,n} |c*m - u(i)|^2
>>
>> I'm not sure what you're saying here.  Only the one point (m in
>> your terminology) minimizes the sum of squares of distances.  How
>> do other points on the same line qualify?
>
> I over-simplified by omitting "compared to any other point on that
> circle".  The mean vector is the absolute minimum, but at any radius
> |c*m| the sum above is at a minmum at c*m.

I see.  Not obvious to me that this is true (and I didn't see an
easy proof either).  OTOH certainly it is plausibly true, so for
now I can take your word for it.

>>> This includes, of course, m projected out to the unit circle.
>>>
>>> This distinction between arc lengths and chord lengths helps to
>>> visualise where these averages differ, and why the conventional
>>> average may seem more intuitive.
>>
>> Interesting perspective.  I wouldn't call them chord lengths
>> because I think of a chord as being between two points both on
>> the same circle,
>
> m (the vector) is the centre of mass, but for some c, c*m lies on
> the circle.  All the lines from the data points to c*m are actual
> chords.  The average "time", A, is the point on the circle that
> minimises the sum of squares of the cords between A the t(i).

Minor point:  the center of mass is a point, not a vector.
Because the circle is centered on the origin, it happens that the
point and the vector from the origin to the point have the same
coordinate values, but still points are different from vectors.

> The "other" average, minimises the sum of the of the angular
> distances.

I think you mean it minimizes the sum of the squares of the
angular distances.

>> and the center of mass is never on the unit
>> circle (not counting the case when all the time values are the
>> same).  Even so it's an interesting way to view the distinction.
>
> It's more interesting because it really is about chords!

I don't buy the "really" here.  The center of mass is fundamental
and always well-defined.  Furthermore it works for collections of
points that are not all on the same circle or sphere.  Looking at
the problem in terms of chords seems somewhat artificial, or at
least less fundamental.

>>> Incidentally, I found another book on statistics on spheres, and
>>> that gets the average over in a few paragraphs.  It states,
>>> without considering any alternatives, that the average is the
>>> vector average.  I can't find anyone using or citing the
>>> arc-length minimising average, despite it being natural on a
>>> sphere to find the mid-point of, say, a set of points on the
>>> Earth's surface.
>>
>> Do you mind my asking, which book was that?
>
> http://library.sadjad.ac.ir/opac//temp/19108.pdf

That's great, thank you.

>> Now that I think about it, finding the point that minimizes the
>> great circle distances squared would be at least computationally
>> unpleasant.  But it could be relevant in some contexts (thinking
>> in particular of astronautics, or, dare I say it, rocket science).
>>
>>> Tim, my best shot at calculating this other average sorts the
>>> points to find the widest gap.  I suspect your algorithm is
>>> similar since you say it is O(n log n).
>>
>> Your instinct that I sorted the time values is right.  If you
>> think a little more I think you will see that the widest gap need
>> not have any particular relationship to where the cut point is.
>> No further elaboration for now so as not to be a spoiler (and I
>> know you like to try figuring things out yourself).
>
> You must be confusing me with someone else!

Oh.  Maybe it was your brother posting in those other messages I
saw coming from your address.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-30 01:00 +0000
  Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-29 23:25 -0800
    Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-30 14:04 +0000
      Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-31 00:24 +0000
        Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-31 06:42 -0800
          Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-12-31 17:04 +0100
            Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-01 01:24 +0000
            Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-08 07:45 -0800
              Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2023-01-08 17:17 +0100
                Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-08 20:41 +0000
                Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2023-01-08 21:14 +0000
                Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2023-01-08 22:31 +0100
                Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-09 03:25 +0000
                Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2023-01-09 11:22 +0100
                Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-09 20:37 +0000
                Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2023-01-10 09:06 +0100
                Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-11 02:41 +0000
                Re: Another little puzzle "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2023-01-11 10:01 +0100
                Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-12 01:00 +0000
                Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-10 23:36 -0800
                Re: Another little puzzle Y A <ya00000100000@yahoo.com> - 2023-01-11 02:39 -0800
          Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-01 01:10 +0000
            Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-08 07:17 -0800
              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-08 19:43 +0000
                Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-08 19:59 +0000
                Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-10 23:25 -0800
      Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-31 06:20 -0800
        Re: Another little puzzle Augǝl <angel0000000001000000000000@mail.ee> - 2022-12-31 10:23 -0800

csiph-web