Find the "largest" dense sub matrix in a large sparse matrix

Posted by BCS on Stack Overflow See other posts from Stack Overflow or by BCS
Published on 2009-08-01T19:59:32Z Indexed on 2010/05/09 4:28 UTC
Read the original article Hit count: 684

Filed under:

sparse-matrix

|

dense-matrix

|

algorithm

|

discrete-mathematics

Given a large sparse matrix (say 10k+ by 1M+) I need to find a subset, not necessarily continuous, of the rows and columns that form a dense matrix (all non-zero elements). I want this sub matrix to be as large as possible (not the largest sum, but the largest number of elements) within some aspect ratio constraints.

Are there any known exact or aproxamate solutions to this problem?

A quick scan on Google seems to give a lot of close-but-not-exactly results. What terms should I be looking for?

edit: Just to clarify; the sub matrix need not be continuous. In fact the row and column order is completely arbitrary so adjacency is completely irrelevant.

A thought based on Chad Okere's idea

Order the rows from largest count to smallest count (not necessary but might help perf)
Select two rows that have a "large" overlap
Add all other rows that won't reduce the overlap
Record that set
Add whatever row reduces the overlap by the least
Repeat at #3 until the result gets to small
Start over at #2 with a different starting pair
Continue until you decide the result is good enough

© Stack Overflow or respective owner

Related posts about sparse-matrix

In R, when using named rows, can a sparse matrix column be added to another sparse matrix?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have two sparse matrices, m1 and m2: > m1 <- Matrix(data=0,nrow=2, ncol=1, sparse=TRUE, dimnames=list(c("b","d"),NULL)) > m2 <- Matrix(data=0,nrow=2, ncol=1, sparse=TRUE, dimnames=list(c("a","b"),NULL)) > m1["b",1]<- 4 > m2["a",1]<- 5 > m1 2 x 1 sparse Matrix of class… >>> More
Find the "largest" dense sub matrix in a large sparse matrix

as seen on Stack Overflow - Search for 'Stack Overflow'
Given a large sparse matrix (say 10k+ by 1M+) I need to find a subset, not necessarily continuous, of the rows and columns that form a dense matrix (all non-zero elements). I want this sub matrix to be as large as possible (not the largest sum, but the largest number of elements) within some aspect… >>> More
MATLAB: Convert two array to a sparse matrix

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm looking for an a command or trick to convert two arrays to a sparse matrix. The two arrays contain x-values and y-values, which gives a coordinate in the cartesian coordinate system. I want to group the coordinates, which if the value is between some value on the x-axes and the y-axes. % MATLAB x_i… >>> More
best way to get a vector from sparse matrix

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have a m x n matrix where each row consists of zeros and same values for each row. an example would be: M = -0.6 1.8 -2.3 0 0 0; 0 0 0 3.4 -3.8 -4.3; -0.6 0 0 3.4 0 0 In this example the first column consists of 0s and -0.6, second 0 and 1.8, third -2.3 and so on. In such case I would like… >>> More
Vectorizatoin of index operation for a scipy.sparse matrix

as seen on Stack Overflow - Search for 'Stack Overflow'
The following code runs too slowly even though everything seems to be vectorized. from numpy import * from scipy.sparse import * n = 100000; i = xrange(n); j = xrange(n); data = ones(n); A=csr_matrix((data,(i,j))); x = A[i,j] The problem seems to be that the indexing operation is implemented… >>> More

Related posts about dense-matrix

Find the "largest" dense sub matrix in a large sparse matrix

as seen on Stack Overflow - Search for 'Stack Overflow'
Given a large sparse matrix (say 10k+ by 1M+) I need to find a subset, not necessarily continuous, of the rows and columns that form a dense matrix (all non-zero elements). I want this sub matrix to be as large as possible (not the largest sum, but the largest number of elements) within some aspect… >>> More
Can a memory page be moved by modifying the page table?

as seen on Stack Overflow - Search for 'Stack Overflow'
Is it possible (on any reasonable OS, preferably Linux) to swap the contents of two memory pages by only modifying the page table and not actually moving any data? The motivation is a dense matrix transpose. If the data were blocked by page size it would be possible to transpose the data within a… >>> More
Matrix multiplication in java (RE-POST)

as seen on Stack Overflow - Search for 'Stack Overflow'
Apologies for the re-post; the earlier time I'd posted I did not have all the details. My colleague, who quit the firm was a C# programmer, was forced to write Java code that involved (large, dense) matrix multiplication. He's coded his own DataTable class in Java, in order to be able to a) create… >>> More
Solving problems involving more complex data structures with CUDA

as seen on Stack Overflow - Search for 'Stack Overflow'
So I read a bit about CUDA and GPU programming. I noticed a few things such that access to global memory is slow (therefore shared memory should be used) and that the execution path of threads in a warp should not diverge. I also looked at the (dense) matrix multiplication example, described in the… >>> More
Is there a Boost (or other common lib) type for matrices with string keys?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a dense matrix where the indices correspond to genes. While gene identifiers are often integers, they are not contiguous integers. They could be strings instead, too. I suppose I could use a boost sparse matrix of some sort with integer keys, and it wouldn't matter if they're contiguous. Or… >>> More