Optimization of 2 matrices

Hi Guys,

I need to solve a problem. I have an idea to do that, just am confused about which functions to use to implement the idea.

So I have 2 matrices. Each matrix contains n rows and 2 columns. The matrix is essentially the x and y co-ordinates of n points. Matrix 1 consists of the co-ordinates at time 't' and Matrix 2 at time 't+Δt'.

The idea.

1.I want to find all possible combinations of the elements in matrix 1 with matrix 2. Since I have 'n' rows, I will have 'n!' combinations.

2. After finding the combinations, I want to calculate the distance between the two points. I use the default formula i.e sqrt((x1-x2)^2+(y1-y2)^2).

3. So i ll have n! n*1 distance matrices. I want to add all the elements in one matrix and then find the matrix that has the least total value amongst all n! matrices.

4. Now the matrix that has the least total distance, I want to take the second matrix (that led to that combination) in my forward calculation.

I am stuck in steps 1, 2 and the final correspondence in step 4. Could anyone tell me what functions I could use to serve my purpose.

Thanks. NS.

I hope I explained the problem clearly.

To simplify things,

if [a b c] and [d e f] are my initial matrices with a-f being the coordinates of points. The matrices are column matrices and should actually contain 2 columns. I have just simplified it. The possible combinations will be [ad be cf], [ad bf ce], [ae bd cf], [ae bf cd], [af bd ce], [af be cd]. After steps 3 and 4, I find that [ae bd cf] gives me the least distance. I want to take the matrix [e d f] in my forward calculations.

[bym]

I don't think your simplification adds anything, in fact it confuses me. You state the matrix 1 & 2 are nx2, yet your example is 1x3??

[NS]

@proecsm. I didnt know how to type in column matrices in this forum. I have stated in my example that they are actually column matrices. To simplify things, i have taken n=3. And 'a-f' are the coordinate pairs.

[John D'Errico]

Um, wrong. Since you have two matrices with n rows in each, all possible combinations will be n^2, NOT n!, i.e., not factorial(n).

[NS]

John, I still think it is n!.

I used solved it using the cases when n=2 and when n=3. In the cases, I got the possible combinations to be 4 and 6. The order is important, so I think these are actually permutations and not combinations. :)

Answer 1

[Matt Fig]

Here is one way to get the permutations:

A = [1 2 3];
B = [4 5 6];
P = perms(1:3);

for ii = 1:size(P,1)
   pairing = [A; B(P(ii,:))]  % Print out just to show the pairing.
   % Do what you will with the pairings steps 2:4?
end

I have a feeling you will do the other steps in the loop as well, but they aren't that clear to me. Perhaps this will give you a start.

%

%

%

%

EDIT

So I think I understand better after some of your comments. This does what you want:

A = rand(3,2); % Matrix one.
B = rand(3,2);  % Matrix two.
P = perms(1:size(B,1));

for ii = 1:size(P,1)
    Dist{ii} = sqrt(sum((A-B(P(ii,:),:)).^2,2));
end

S = cellfun(@sum,Dist);
[M,I] = min(S);

Min_comb = B(P(I,:),:)  % This has the minimum combination.

Note that if you don't need S or Dist for future use, this simplifies to:

mn = inf;

for ii = 1:size(P,1)
    tmp = sum(sqrt(sum((A-B(P(ii,:),:)).^2,2)));
    if tmp<mn
        mn = tmp;
        idx = ii;
    end
end

Min_comb = B(P(idx,:),:)  % This is the one you want.

[NS]

It worked for a random case that I took. I ll try implementing it in my main code and let you know. Thanks Matt. :)