Select dominated columns in a large matrix

Consider a MxN real valued matrix F with nonnegative elements. I say that a column Fn is dominated if there is another column which has all elements greater than Fn.

A simple way to find the set of dominated columns is

 z=zeros(1,size(F,2)); 
 for j=1:size(F,2); 
     z(j)=max(min((F-F(:,j)))>0); 
 end

However, I need to do it for very large F (say 10,000 x 500,000). What is a more efficient way to do it?

[Matt J]

(say 10,000 x 500,000)

If so, then this would be a sparse matrix?

If not, then you have 37 GB to hold such a matrix in double floats?

And if it is sparse, what is the sparsity? And are the zero-elements to be included in the determination of whether a column is dominated?

[valentino dardanoni]

Unfortunately it is not sparse, but I have 128 GB of memory

Answer 1

[Image Analyst]

How about (untested)

[rows, columns] = size(F)
itsDominated = false(1, columns); % Keep track of which columns are dominated.
for col = 1 : columns
    % Get one columns to check.
    thisColumn = F(:, col);
    % Check it against all other columns.
    for col2 = 1 : columns
        if col2 == col
            continue; % Don't check column against itself.
        end
        fprintf('Checking column %d against column %d.\n', col, col2);
        % See if all the values of column2 are greater than the column
        % we're checking on.
        thisColumn2 = F(:, col2);
        isDom = all(thisColumn2 > thisColumn);
        if isDom
            % It's dominated.  Log this fact and then skip on to the next
            % reference column.
            itsDominated(col) = true;
            fprintf('   Column %d dominates column %d.\n', col2, col);
            % Break out of the col2 loop.
            break; % Don't bother checking any other columns against this one.
        end
    end
end

[valentino dardanoni]

Thank you, I am testing it against my naive implementation, will let you know the difference....

[Image Analyst]

Here is a small test case that shows my code works:

% Make sample Data
F = randi(99, 10, 8);
% Make column 5 dominant to column 1
F(:, 5) = F(:, 1) + 1;
% Make column 6 dominant to column 2
F(:, 6) = F(:, 2) + 1;
% Make column 7 dominant to column 4
F(:, 7) = F(:, 4) + 1

F = 10×8

67 89 46 45 68 90 46 23 77 47 48 1 78 48 2 44 50 29 8 11 51 30 12 45 99 88 85 56 100 89 57 38 98 56 39 90 99 57 91 65 37 17 47 59 38 18 60 41 73 86 25 96 74 87 97 60 15 42 19 4 16 43 5 77 80 15 61 34 81 16 35 84 56 39 50 27 57 40 28 69

[rows, columns] = size(F);
itsDominated = false(1, columns); % Keep track of which columns are dominated.
for col = 1 : columns
    % Get one columns to check.
    thisColumn = F(:, col);
    % Check it against all other columns.
    for col2 = 1 : columns
        if col2 == col
            continue; % Don't check column against itself.
        end
        fprintf('Checking column %d against column %d.\n', col, col2);
        % See if all the values of column2 are greater than the column
        % we're checking on.
        thisColumn2 = F(:, col2);
        isDom = all(thisColumn2 > thisColumn);
        if isDom
            % It's dominated.  Log this fact and then skip on to the next
            % reference column.
            itsDominated(col) = true;
            fprintf('   Column %d dominates column %d.\n', col2, col);
            % Break out of the col2 loop.
            break; % Don't bother checking any other columns against this one.
        end
    end
end

Checking column 1 against column 2.
Checking column 1 against column 3.
Checking column 1 against column 4.
Checking column 1 against column 5.

   Column 5 dominates column 1.

Checking column 2 against column 1.
Checking column 2 against column 3.
Checking column 2 against column 4.
Checking column 2 against column 5.
Checking column 2 against column 6.

   Column 6 dominates column 2.

Checking column 3 against column 1.
Checking column 3 against column 2.
Checking column 3 against column 4.
Checking column 3 against column 5.
Checking column 3 against column 6.
Checking column 3 against column 7.
Checking column 3 against column 8.
Checking column 4 against column 1.
Checking column 4 against column 2.
Checking column 4 against column 3.
Checking column 4 against column 5.
Checking column 4 against column 6.
Checking column 4 against column 7.

   Column 7 dominates column 4.

Checking column 5 against column 1.
Checking column 5 against column 2.
Checking column 5 against column 3.
Checking column 5 against column 4.
Checking column 5 against column 6.
Checking column 5 against column 7.
Checking column 5 against column 8.
Checking column 6 against column 1.
Checking column 6 against column 2.
Checking column 6 against column 3.
Checking column 6 against column 4.
Checking column 6 against column 5.
Checking column 6 against column 7.
Checking column 6 against column 8.
Checking column 7 against column 1.
Checking column 7 against column 2.
Checking column 7 against column 3.
Checking column 7 against column 4.
Checking column 7 against column 5.
Checking column 7 against column 6.
Checking column 7 against column 8.
Checking column 8 against column 1.
Checking column 8 against column 2.
Checking column 8 against column 3.
Checking column 8 against column 4.
Checking column 8 against column 5.
Checking column 8 against column 6.
Checking column 8 against column 7.

[valentino dardanoni]

Thank you very much Image Analiyst... Yes, it works perfectly, I run it and timed it, now I am timing my naive method, I am acceptingbyour answer and I will let you know later the psedd inv=crease

[Image Analyst]

OK, thanks. I tought my method was "naive". It's not particularly clever. It's basically just a brute force comparison method. About the only clever things about it might be bailing out after the first dominant row is found, and the use of all().

You could speed it up quite a bit by getting rid of the fprintf() statements.