CODEWITHSUNDEEP
matlabmatrix
Karnivaurus
Karnivaurus

Reputation: 24121

Finding sub-matrix with minimum elementwise sum

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!

Upvotes: 3

Views: 1009

Answers (3)

Daniel1000
Daniel1000

Reputation: 797

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.

Upvotes: 4

patrik
patrik

Reputation: 4558

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.

Upvotes: 1

ewz
ewz

Reputation: 423

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,:))

Upvotes: 1

Related Questions