Dimensionality reduction on a huge binary matrix

Question

I have a 0/1 sparse matrix with 500 k columns and 3 M rows and I want to do reduce the number of columns.

Clearly I cannot load this into R, as is, so prcomp is out. (I cannot even create the Gram matrix in R: too many elements specified.)

However, it appears that I should be able follow this path:

1. Reduce the number of columns to 200 k by dropping very sparse ones
2. Compute the Gram matrix by scanning the input file without loading the whole thing
3. Compute the Gram matrix eigenvectors in R.

Any better suggestions?

Answer 1

Nystrom Approximation based large scale SVD and Column sampling based SVD are used in this scenario. Check out sections 3.1, 3.2 and 3.3 in "Large-Scale Manifold Learning" by Ameet Talwalkar, Sanjiv Kumar and Henry Rowley. These methods sample columns of a large matrix and approximate the spectral decomposition, and have been used for large scale dimensionality reduction (the scale you have mentioned) and manifold learning problems in statistics and machine learning.

Example manifold learning paper:Hessian Eigenmaps by Donoho and Grimes at Stanford: http://www-stat.stanford.edu/~donoho/Reports/2003/HessianEigenmaps.pdf

Answer 2

Binary pack the data. That was the approach I used for the Netflix prize data set. In that scenario though I was using my own code to do the matrix factorisation, whereas if you wish to use off the shelf algorithms you may still be able to do this if you can find some sensible implementation built on an interface for representing a binary matrix (e.g. IBinaryMatrix).

The idea is that you assign each of the 500k columns an ID, such that each row then contains an ID only for those elements that are set to one (variable length rows), AKA a jagged 2D array.

You can choose to represent the IDs with the bare minimum of bits required and pack/unpack them with slightly fiddly bit shifting and masking, or pad them to 8, 16 or 32 bits if you don't need to the additional packing density.