Finding unique pairs of samples with minimum distance

Question

I need to match the samples in two datasets. What I have is the distance between all the samples in the dataset and arrange them in a matrix as shown below. There can be different number of samples hence it is not a square matrix. For example,

    3 4 
    6 2 
    1 9 

Its a 3 by 2 matrix defining distance between samples in two datasets. I need to select the pairs of samples having minimum distance such that one sample is not selected twice. Here, my answers would be 3 and 1; 2 and 2. The 1st item in the first is left out as it does not have minimum with other samples. However, I also need to know which samples was not selected. Is there a shortcut method to accomplish this in matlab.

Answer 1

I believe that this problem is known as minimum weight bipartite matching. I am not sure whether Matlab provides an algorithm for that out-of-the-box, but I found (not tested, though) an implementation here: http://www.mathworks.com/matlabcentral/fileexchange/11609