Select dominated columns in a large matrix

Question

valentino dardanoni 2023-12-18

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2061832-select-dominated-columns-in-a-large-matrix

评论： Image Analyst 2023-12-19

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?

2 个评论
显示无隐藏无

Matt J 2023-12-18

编辑：Matt J 2023-12-18

(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 2023-12-18

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Image Analyst 2023-12-18

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2061832-select-dominated-columns-in-a-large-matrix#answer_1373747

在 MATLAB Online 中打开

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

4 个评论
显示 2更早的评论隐藏 2更早的评论

Image Analyst 2023-12-19

在 MATLAB Online 中打开

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 2023-12-19

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 2023-12-19

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.

请先登录，再进行评论。

Select dominated columns in a large matrix

2 个评论
显示无隐藏无

采纳的回答

4 个评论
显示 2更早的评论隐藏 2更早的评论

更多回答（0 个）

另请参阅

类别

标签

Community Treasure Hunt

Select dominated columns in a large matrix

2 个评论 显示 无隐藏 无

采纳的回答

4 个评论 显示 2更早的评论隐藏 2更早的评论

更多回答（0 个）

另请参阅

类别

标签

Community Treasure Hunt

2 个评论
显示无隐藏无

4 个评论
显示 2更早的评论隐藏 2更早的评论