R Recommender System for very sparse matrices required
I would look into the Soft Imputation method that has an implementation in R. It uses iterative soft-thresholding to compute missing values. Calculations are done with a matrix class called "Incomplete" to deal large sparse matrices and allows for quick calculation of scaling/centering rows and columns.

I've had good success using this completing a 10,000 by 10,000 very sparse matrix so I'd imagine it should do fairly well with your dataset.