Alex Rivera | Logout

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

Asked 2009-08-01T19:59:32.653
12

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

  1. Order the rows from largest count to smallest count (not necessary but might help perf)
  2. Select two rows that have a "large" overlap
  3. Add all other rows that won't reduce the overlap
  4. Record that set
  5. Add whatever row reduces the overlap by the least
  6. Repeat at #3 until the result gets to small
  7. Start over at #2 with a different starting pair
  8. Continue until you decide the result is good enough
algorithm discrete-mathematics sparse-matrix
Edit
Report

1 Answer

1

Is this a Netflix problem?

MATLAB or some other sparse matrix libraries might have ways to handle it.

Is your intent to write your own?

Maybe the 1D approach for each row would help you. The algorithm might look like this:

  1. Loop over each row
  2. Find the index of the first non-zero element
  3. Find the index of the non-zero row element with the largest span between non-zero columns in each row and store both.
  4. Sort the rows from largest to smallest span between non-zero columns.

At this point I start getting fuzzy (sorry, not an algorithm designer). I'd try looping over each row, lining up the indexes of the starting point, looking for the maximum non-zero run of column indexes that I could.

You don't specify whether or not the dense matrix has to be square. I'll assume not.

I don't know how efficient this is or what its Big-O behavior would be. But it's a brute force method to start with.

answered 2009-08-01T20:18:46.110

Your Answer