Finding Spatial Median By Optimization

So I am trying to create a program to calculate the L-1 spatial median for a given set of data, which is stored in a matrix, A, with each column being a data point. In order to do this I need to try find the vector that minimizes the sum of the distances from each data point to that point. In order to do this I wrote a program, which breaks the data matrix A into data points by breaking it into column matrices, and then it calculates the distance from the independent variable, X and sums these all up. My code for this is:

function[Y] = vedian(X,A) 
  Y = sum(arrayfun(@(nc) norm(X-A(:,nc)),1:size(A,2)));
end

So to find the median for the data set A, I need to minimize this function, and so I tried doing this:

function[X,fval] = runvedian(X0,A)
  [X,fval] = fminunc(@(X) vedian(X,A), X0);
end
function[Y] = vedian(X,A) 
  Y = sum(arrayfun(@(nc) norm(X-A(:,nc)),1:size(A,2)));
end

However, the optimization process does seem to work. For example, if we use A = [1 3;0 0] the median should obviously be the point [2,0] as this is just the basic 1-Dimensional median. However when I used either fminunc or fminsearch I get that X=.75, which is just plan wrong and non-senscial since the operation of subtraction should not be defined for .75 and a 2x1 matrix. Can anyone spot the problem causing this, or suggest a better way to go about this?

Answer 1

[Andrew Newell]

The problem is just ill-defined for two points because, for a <= x <= b, |x-a| + |x-b| = x-a+b-x = b-a. What surprises me is that you got an answer outside of the interval [1 3]. When I try it on 3 or more points, your code seems to work fine.

Answer 2

[Walter Roberson]

MATLAB defines binary arithmetic between a scalar and a matrix as if the scalar were replicated to the size of the matrix.

In this thread and the previous thread you have not been clear about what your X0 is, which makes it more difficult to debug your problem.

Answer 3

[Ramin K.Badri]

Hi,

As I know about the L1-median, this method has nonuniqueness problem for univariate median. It turns out that this is the only situation where nonuniqueness can arise as shown in Milasevic and Ducharme (1987). However, L1 median is the only known (proved) multidimensional median which possesses the uniqueness property (Zuo, 2013)

Read Y. Zuo / Computational Statistics and Data Analysis 66 (2013) 82–88 for more information.

I hope it would be helpful.