Finding the densest n * n submatrix in a sparse matrix
I have a sparse square matrix with a side of 2 * n.
eg.
1,0,0,1,0,1 0,1,1,1,0,1 1,0,0,0,1,1 0,0,1,1,0,0 1,1,1,0,0,0 0,0,0,1,1,0
And I need an efficient way to find the n * n submatrix with the largest number of 1s.
I found several ways to do this, but not faster than O (n ^ 4). I also found faster ways without requiring the submatrix to be n * n.
EDIT: The submatrix must be contiguous,
source to share
Based on your application for an O (n ^ 4) -time algorithm, my guess is that the submatrix must be contiguous, since otherwise the problem is NP-hard (it's harder than biclik detection). For the O (n ^ 2) -time algorithm, it suffices to perform O (n ^ 2) preprocessing, which allows O (1) -time queries of the form "given a, b, c, d
, compute sum_{i=a}^b sum_{j=c}^d X[i,j]
".
Given an array X[1..m,1..n]
, compute the array Y[0..m,0..n]
as follows.
initialize Y to the zero array
for i from 1 to m
for j from 1 to n
Y[i,j] = Y[i-1,j] + X[i,j]
end
end
for i from 1 to m
for j from 1 to n
Y[i,j] = Y[i,j-1] + Y[i,j]
end
end
Now Y[c,d] = sum_{i=1}^c sum_{j=1}^d X[i,j]
. To calculate sum_{i=a}^b sum_{j=c}^d X[i,j]
, use the inclusion of exception Y[c,d] - Y[a-1,d] - Y[c,b-1] + Y[a-1,b-1]
.
source to share