3

I have a symmetric m-by-m matrix A. Each element has a value between 0 and 1. I now want to choose n rows / columns of A which form an n-by-n sub-matrix B.

The criteria for choosing these elements, is that the sum of all elements of B must be the minimum out of all possible n-by-n sub-matrices of A.

For example, suppose that A is a 4-by-4 matrix:

A = [0 0.5 1 0; 0.5 0 0.5 0; 1 0.5 1 1; 0 0 1 0.5]

And n is set to 3. Then, the best B is the one taking the first, second and fourth rows / columns of A:

B = [0 0.5 0; 0.5 0 0; 0 0 0.5]

Where the sum of these elements is 0 + 0.5 + 0 + 0.5 + 0 + 0 + 0 + 0 + 0.5 = 1.5, which is smaller than another other possible 3-by-3 sub-matrices (e.g. using the first, third and fourth rows / columns).

How can I do this?

This is partly a mathematics question, and partly a Matlab one. Any help with either would be great!

Karnivaurus
  • 22,823
  • 57
  • 147
  • 247
  • how is `A` symmetric? – Robert Seifert Jul 29 '14 at 17:03
  • The i^th row and i^th column are the same, so `A` is equal to the transpose of `A`. Right? – Karnivaurus Jul 29 '14 at 17:06
  • Yes sorry, my mistake, got confused. – Robert Seifert Jul 29 '14 at 17:13
  • But isn't the B in your example actually `B = [0 0.5 1; 0.5 0 0.5; 1 0.5 1]`? What am I missing? – Robert Seifert Jul 29 '14 at 17:21
  • I think the B value is correct (meaning that it is the correct matrix subset per the definition), it is just created with the first, second and fourth rows/ columns. (not first, second and third) – ewz Jul 29 '14 at 17:48
  • The row and column numbers to be chosen from `A` must be the same? That is can't we have like `1,3,4` rows and `2,3,4` columns, if they yield the minimum sum of its elements as compared to the rest of the combinations? – Divakar Jul 29 '14 at 18:35
  • @Divakar Perhaps the symmetry of `A` allows one to discard solutions with different column and row indices? – Luis Mendo Jul 29 '14 at 18:43
  • @LuisMendo That could be it! But must had been specified. – Divakar Jul 29 '14 at 18:45
  • @Divakar Yes. The question should be clearer – Luis Mendo Jul 29 '14 at 18:45
  • The accepted answer by@DanielF. works well with a small matrix. However, I want to solve a similar problem in relation to a *151*-by-*151* matrix, which I wrote about at http://stackoverflow.com/questions/33738857/matlab-find-abbreviated-version-of-matrix-that-minimises-sum-of-matrix-elements. When I apply the answer by @DanielF. I run into a problem because the `nchoosek` is too large. Is there any solution that will also work for a large matrix? – user1205901 - Слава Україні Nov 17 '15 at 01:03

3 Answers3

4

Do the following:

m = size(A,1);
n=3;
sub = nchoosek(1:m,n); % (numCombinations x n)
subR = permute(sub,[2,3,1]); % (n x 1 x numCombinations), row indices
subC = permute(sub,[3,2,1]); % (1 x n x numCombinations), column indices
lin = bsxfun(@plus,subR,m*(subC-1)); % (n x n x numCombinations), linear indices
allB = A(lin); % (n x n x numCombinations), all possible Bs
sumB = sum(sum(allB,1),2); % (1 x 1 x numCombinations), sum of Bs
sumB = squeeze(sumB); % (numCombinations x 1), sum of Bs
[minB,minBInd] = min(sumB);
fprintf('Indices for minimum B: %s\n',mat2str(sub(minBInd,:)))
fprintf('Minimum B: %s (Sum: %g)\n',mat2str(allB(:,:,minBInd)),minB)

This looks only for submatrices where the row indices are the same as the column indices, and not necessarily consecutive. That is how I understood the question.

Daniel1000
  • 779
  • 4
  • 11
  • By convolve the `A` matrix you do not need to search for all combinations. Check my solution below. It works! – patrik Jul 30 '14 at 10:44
1

This is a bit brute force, but should work

A = [0 0.5 1 0; 0.5 0 0.5 0; 1 0.5 1 1; 0 0 1 0.5];

sizeA = size(A,1);
size_sub=3;


idx_combs = nchoosek(1:sizeA, size_sub);

for ii=1:size(idx_combs,1)
    sub_temp = A(idx_combs(ii,:),:);
    sub = sub_temp(:,idx_combs(ii,:));

    sum_temp = sum(sub);
    sums(ii) = sum(sum_temp);
end

[min_set, idx] = min(sums);

sub_temp = A(idx_combs(idx,:),:);
sub = sub_temp(:,idx_combs(idx,:))
ewz
  • 423
  • 2
  • 5
1

Try to convolve the matrix A with a smaller matrix M. Eg if you is interested in finding the 3x3 submatrix then let M be ones(3). This code shows how it works.

A = toeplitz(10:-1:1) % Create a to eplitz matrix (example matrix)
m = 3; % Submatrix size
mC = ceil(m/2); % Distance to center of submatrix
M = ones(m);
Aconv = conv2(A,M); % Do the convolution.
[~,minColIdx] = min(min(Aconv(1+mC:end-mC,1+mC:end-mC))); % Find column center with smallest sum
[~,minRowIdx] = min(min(Aconv(1+mC:end-mC,minColIdx+mC),[],2)); % Find row center with smlest sum
minRowIdx = minRowIdx+mC-1 % Convoluted matrix is larger than A
minColIdx = minColIdx+mC-1 % Convoluted matrix is larger than A
range = -mC+1:mC-1
B = A(minRowIdx+range, minColIdx+range)

The idea is to imitate a fir filter y(n) = 1*x(n-1)+1*x(n)+1*x(n+1). For now it only finds the first smallest matrix though. Notice the +1 adjustment because first matrix element is 1. Then notice the the restoration right below.

patrik
  • 4,506
  • 6
  • 24
  • 48
  • Ok the code is edited and works now, sorry. The advantage is that this code is simple in the sense that no complcated and hard to understand functions are used. I am not sure in terms of efficiency, but convolution should be quite effective. It is at least 500 times faster than @Daniel. – patrik Jul 30 '14 at 10:34
  • Also if all combinations are wanted, the find(myMtx = min(myMtx)) can be used. However, normally you will not have sub matrices with equal sum. – patrik Jul 30 '14 at 10:46
  • I understood the question such that the row and column indices must be the same. Besides, as I used A=rand(10) as a test matrix, I got a smaller sum(B(:)) with my code. – Daniel1000 Jul 30 '14 at 18:51