"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2023-01-09 21:37, Ben Bacarisse wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>
>>> On 2023-01-09 04:25, Ben Bacarisse wrote:
>>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>>>
>>>>> On 2023-01-08 21:41, Ben Bacarisse wrote:
>>>>>
>>>>>> But
>>>>>> the problem is /finding/ a specific average -- the point (or angle) that
>>>>>> minimises the sum of squares of the distances (or angles) from that
>>>>>> average point (or angle).
>>>>>
>>>>> That is not a programming problem. It is a problem space's one. You
>>>>> must go to the corresponding part of science or engineering or
>>>>> economics etc and formulate it there in terms of that space.
>>>> I don't follow. It's a mathematical problem for which an algorithm is
>>>> sought.
>>>
>>> Firstly, this is comp.programming group.
>> Do you consider discussion algorithms off topic here? Seriously?
>
> No, I consider off topic discussing mathematical problems /=
> algorithms. You did not discuss any algorithms so far.

Algorithms don't come out of thin air. The objective must be discussed
first. You can't seriously think that everyone here should remain
silent until, out of nowhere, someone says "consider this algorithm to
find the average of a set of points".

>>> Secondly, if algorithm is sought then there must be a mathematical
>>> formulation of what a numeric solution is sought for.
>> There needs to be a problem statement that can be discussed and refined.
>> The original post about circular averages has led to two different
>> refinements -- the vector average (projected onto the unit circle) and
>> the arc-length average. Both generalise to more dimensions and I
>> happened to mention in passing that the great-circle average would be a
>> natural fit in some situations.
>
> I missed generalization to 3D. Sorry.
> [You kept on writing about unit *circle* and an angle, where it
> actually meant unit sphere and polar angles/spherical coordinates]

Both have been discussed, but I think I've been clear about which one I
am talking about.

>> Tim mentioned (again in passing) that it looks hard. You seemed to
>> suggest it was not, but I am not sure you knew what the problem was at
>> that time.
>> All of this seems to be to be exactly what comp.programming should be
>> about.
>
> Differential geometry and spherical trigonometry are certainly off
> topic.

I don't think I discussed either.

>>> (Finding a minimum is an optimization problem, there are thousands of
>>> algorithms already)
>> Programmers should know that specifications are not algorithm designs.
>
> Who said they are?

I explained in the text you cut. Maybe your reference to the thousands
of minimisation algorithms was just an off the cuff remark, but it reads
as if you were suggesting using one as them as the solution to this
programming task.

>>>> I don't see any connection to some science or engineering
>>>> space. If it /came/ from some scientific study, it has already been
>>>> turned into what the programmer needs come up with.
>>>>
>>>>> Average is just such formulation of finding a representative member
>>>>> from some set having some specific properties. E.g. least squares in
>>>>> physics usually has the meaning of least energy etc. So, it goes in
>>>>> this order (not in reverse):
>>>>>
>>>>> 1. You need the least energy representative.
>>>>> 2. An average gives you that.
>>>>> 3. You measure the inputs.
>>>>>
>>>>> After that you ask yourself given these measures how to compute the
>>>>> average? And only now it becomes a programming issue.
>>>> So if I asked you for code to calculate the arithmetic mean of an array
>>>> of numbers you would ask for all this first, declaring it not yet a
>>>> programming issue?
>>>
>>> Then I would ask you, if this is a solution, what was the problem?
>> This is a solution to the simpler problem.
>
> And what was that the problem? [Adjective adds/clarifies nothing]
>
>> But we are not in that situation. A few knowledgeable and experienced
>> people are discussing a programming problem.
>
> I saw no discussion on programming so either.
>
>> You are welcome to join
>> in, but the best way for you to do that is to ask whatever questions you
>> think would help you understand what's being discussed. So far, your
>> replies have alternated between "it's trivial" and "it's unstated".
>
> Yes, because you wrote about minimum of arc length on a *circle*. And
> that is trivial.

I think I have been clear that the problem you claimed was trivial was
about points on a sphere.

But the circle version is not trivial in the sense you seem to think it
is. What you say below about seems to miss the key issue altogether.

>>>>>> You say you need a formula, so I'll try... Let P_n be a collection of n
>>>>>> unit vectors specifying n points on a unit sphere. Find the unit vector
>>>>>> A that minimises
>>>>>> Sum_{i=1,n} ( arctan( |A x P_n| / A . P_n ) )^2
>>>>>> (arctan is the "all quadrant" version that is often called atan2 in
>>>>>> programming languages.)
>>>>>
>>>>> 1. atan2 has two arguments (the adjacent and the opposite legs);
>>>> Obviously I can't guess how much I can safely assume so I expected there
>>>> might be questions. arctan(p / q) is usually coded as atan2(p, q).
>>>>
>>>>> 2. What is "A";
>>>> The unit vector that is being sought -- the result of the algorithm. It
>>>> represents a point on the unit sphere that is the desired average of the
>>>> input points.
>>>>
>>>>> 3. What operations(?) "x" and "." denote?
>>>> x denotes the cross product, and . the dot product.
>>>> Do you agree that this is not a trivial problem? If not, please give
>>>> the trivial algorithm!
>>>
>>> If I correctly understood your explanation (and with a few obvious
>>> corrections):
>>>
>>> Sum atan2 (|A x Pi|, A · Pi) --> min
>>> i=1..n {A | A on the circle}
>> No. A is a vector denoting a point on the unit sphere. And you have
>> missed out the power of two. Were these changes what you call "obvious
>> corrections"?
>>
>>> |A x Pi| = |A| |Pi| |sin θi| (θi is the angle between the vectors A and Pi)
>>>
>>> A · Pi = |A| |Pi| cos θi
>>>
>>> atan2 (|A x Pi|, A · Pi) = atan2 (|sin θi|, cos θi) = θi'
>>>
>>> Where θi' is θi with lower semicircle mapped to the upper one (for
>>> whatever reason).
>>>
>>> (If mapping was unintended you must have taken the direction of the
>>> cross product for the sign for |A x Pi|)
>>>
>>> On a circle varying the angle between A and (R, 0), where R is the
>>> radius, you find that the mean of the angles between Pi and (R, 0)
>>> yields the minimum.
>> This does not even solve the related case of finding the average point
>> on the unit circle.
>
> It elementary does for both formula you gave (after corrections) and
> the circumference:
>
> Sum Length_Of_Arc (Pi, A)^2 =
> i=1..n
>
> = Sum (R Angle (Pi, A))^2 =
> i=1..n
>
> = R^2 Sum ((Angle (Pi, (R, 0)) - Angle (A, (R, 0)))^2
> i=1..n

There's no need to bring R into it. Either accept that this is a unit
circle or consider only the angles.

> (R, 0) denotes vector x = R, y = 0. Let θi denote Angle (Pi, (R, 0))
> and α do Angle (A, (R, 0)) then

Simpler to start from here -- to find the average of the angles -- the
angle that minimises the sum of squares of angular differences:

> = R^2 Sum (θi - α)^2 --> min
> i=1..n
>
> Derivative d/dα:
>
> 2 R^2 Sum (θi - α) = 0 <=> (R /= 0)
> i=1..n
>
> <=> Sum θi - nα = 0 <=>
> i=1..n
>
> <=> α = Sum θi / n = mean ({θi})
> i=1..n
>
> The angle between A and (R, 0) is the mean of angles of points.

I don't think you have grasped the basic problem. If you want to
consider the circular case you'll have to review the posts that were
specifically about it. You seem to be suggesting that a conventional
mean solves the problem.

> Anyway, there are lengthy papers on spherical averages introducing
> iterative solutions, some with source code for the algorithms. That is
> the right way to compute it, if you really wanted...

I'd like to read one. Do you have a citation, please? The only
treatments I've found don't discuss the average that Tim and I were
talking about. They only consider the simple vector average. (But I've
only found two.)

> [Again, it is not programming. In case of spherical geometry a
> programmer will find an expert mathematician and who will have the
> problem properly stated.

The problem has been properly stated. We seek an algorithm that finds a
point that minimises the sum of squares of the great-circle distances
between that point and the input points. You could have asked if any of
this was unclear. To me it is both clear and intuitive.

> The next stop is by an expert applied mathematician who will outline a
> workable numeric solution. Then the programmer can start.]

Ah, you hand off the task of devising algorithms to mathematicians?
That would make programming very dull. Anyway, you would not tackle
this sort of problem until an expert applied mathematician has done
everything except code up a workable numerical solution. Is that also
the case for the average angle problem?

--
Ben.