"Densifying" very large sparse matrices by rearranging rows/columns
<p>I have a very large sparse matrix (240k*4.5k, â¤1% non-zero elements), which I would like to "densify" by rearranging its rows and columns in a way that the upper left region is enriched in non-zero elements as much as possible. (To make it more manageable and visually assessable.) I would prefer <code>scipy</code> and related tools to do this.</p>

<ul>
<li>A good suggestion was already made <a href="http://stackoverflow.com/questions/15155276/rearrange-sparse-arrays-by-swapping-rows-and-columns">here</a> for a solution to "manually" swap rows/columns of sparse matrices, but it does not cover the challenge of identifying which rows/columns to swap to get an optimal enrichment (dense block) in the upper left corner.</li>
<li>Note that a simple sorting of rows/columns based on the number of non-zero elements does not solve the problem. (If I take <em>e.g.</em> the two rows with the most elements, there will not necessarily be any overlap between them in terms of where - <em>i.e.</em> in which columns - are the elements located.)</li>
<li>I'm also curious about the optimal sparse matrix representation in <code>scipy.sparse</code> for this task.</li>
</ul>

<p>Any suggestions or specific implementation ideas are welcome.</p>

<p>It looks like you can already swap rows preserving sparsity so the missing part is the algorithm to sort the rows. So you need a function that gives you a "leftness" score. A heuristic that could work is the following:</p>

<ol>
<li>first get a mask of the non-zero elements (you don't care about the actual values, only about its non-zeroness).</li>
<li><p>Estimate the density distribution of the non-zero values along the column axis:</p>

<pre><code>def density(row, window):
    padded = np.insert(row, 0, 0)
    cumsum = np.cumsum(padded) 
    return (cumsum[window:] - cumsum[:-window]) / window
</code></pre></li>
<li><p>Calculate the leftness score as the column with the maximum left-penalised density (looking from the right):</p>

<pre><code>def leftness_score(row):
    n = len(a)
    window = n / 10   # 10 is a tuneable hyper parameter
    smoothness = 1    # another parameter to play with
    d = density(row)
    penalization = np.exp(-smoothness * np.arange(n))
    return n - (penalization * d).argmax()
</code></pre></li>
</ol>

<p>This algorithm gives higher score to rows having a high density of values as long as the max value of this density is not too far to the right. Some ideas to take it further: improve the density estimation, play with different penalization functions (instead of neg exp), fit the parameters to some synthethic data reflecting your expected sorting, etc. </p>

python numpy matrix scipy scikit-learn