Select dominated columns in a large matrix

2023 12 18
1 个回答
回答已采纳
更新时间：2023 12 19
16 次查看（30 天）

0 个投票

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
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
valentino dardanoni 2023-12-18
Unfortunately it is not sparse, but I have 128 GB of memory

请先登录，再进行评论。

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

 采纳的回答

Image Analyst
Image Analyst 2023-12-18

0 个投票

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更早的评论

valentino dardanoni
valentino dardanoni 2023-12-18
Thank you, I am testing it against my naive implementation, will let you know the difference....
Image Analyst
Image Analyst 2023-12-19
Ran in:
Ran in:
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
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
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.

请先登录，再进行评论。

更多回答（0 个）

类别

在 帮助中心 和 File Exchange 中查找有关 Animation 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by