On Tuesday 04 December 2007, Fred lunnon wrote:
It's not at all obvious whether this function has multiple (local) minima --- in which case it may be nontrivial to compute. Almost certainly, the sum of the squares of the distances would be more tractable.
Well, yes. Minimizing the sum of squared distances gives the centroid.
What relation might these definitions bear to the convex hull stripping algorithm mentioned earlier?
I rather suspect the answer is "none, except by coincidence, in dimensions > 1" but haven't much actual argument to back up that suspicion.
On 12/3/07, Steve Witham <sw@tiac.net> wrote:
My friend Richard Harter redefined my median in what may be a nicer way:
We use the sum of absolute distances function,
f(x) = sum(abs(x-x_i))
and find the set of x's such f(x) is a minimum. All of these are valid medians; however the centroid of the set is in some sense the most central median.
The centroid needn't be a median in this sense at all in dimensions other than 1. In two dimensions, suppose your points consist of the vertices of a regular 999-gon inscribed in |z|=1, together with a single point at (10^6,0). Then the centroid is (1000,0) but f(1000-h,0) is approximately f(1000,0) - 998h and so the centroid isn't even a local minimum of f. In one dimension, the contribution to f from any two points is constant between the two points and increases as you move away from either. In other words, in one dimension f is constant inside the convex hull and increases as you move outside it. Therefore, the convex hull stripping algorithm gives the same results as f-minimizing does in one dimension. Of course the corresponding property doesn't hold for f even in two dimensions. In fact, if g from R^2 to R has the property that sum_A g(x-a) is constant when x is a convex combination of the elements of A, then I claim g is constant; consider any y and consider A0 = {y,wy,w^2y} and A1 = A0 u {-y} where w is a nontrivial cube root of 1; then 0 is a convex combination of the elements of A0 and also of those of A1; subtracting two functions that are constant near 0, we find that g(h+y) is constant for h near 0 and hence that g is constant near y; so g is everywhere locally constant and therefore globally constant. (Note that this still works if we impose our condition only in the special case where no element of A is a convex combination of the others.) Is there some f of less simple form with some such property that would let us play the hull-stripping game? -- g