# Dimensionality reduction on a huge binary matrix

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?

-
What do you intend to do with this matrix? How is this question related to statistical and data analysis? –  whuber Aug 23 '12 at 19:48

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

-