I have a dataset with ~1M rows and ~500K sparse features. I want to reduce the dimensionality to somewhere in the order of 1K-5K dense features.
sklearn.decomposition.PCA doesn't work on sparse data, and I've tried using sklearn.decomposition.TruncatedSVD but get a memory error pretty quickly. What are my options for efficient dimensionality reduction on this scale?
Have you heard of Uniform Manifold Approximation and Projection (UMAP)?
UMAP (Uniform Manifold Approximation and Projection) is a novel manifold learning technique for non-linear dimension reduction. UMAP is constructed from a theoretical framework based in Riemannian geometry and algebraic topology. The result is a practical scalable algorithm that applies to real world data. The UMAP algorithm is competitive with t-SNE for visualization quality, and arguably preserves more of the global structure with superior run time performance. Furthermore, UMAP as described has no computational restrictions on embedding dimension, making it viable as a general purpose dimension reduction technique for machine learning.
Check their code and original paper for list of pros and cons, it is super easy to use.
Quick Facts: UMAP can handle large datasets and is faster than t-SNE and also supports fitting to sparse matrix data, and contrary to t-SNE, a general purpose dimension reduction technique, meaning that not only it can be used for visualisation but also for reducing the feature space for feeding into other machine learning models.
Concrete Examples: I have benchmarked the method and compared it against some other dimensionality reduction techniques benchmark notebook, if interested to have a quick look and a jump start.
Just in case people coming across this post find UMAP to be not efficient enough, here's some other techniques that I came across that are even more efficient (but not as high quality):
Random Projection: Essentially make a random matrix of shape $ d~\times~m$ where $d$ is the original dimensionality and $m$ is the desired dimensionality, and multiply the data matrix with the projection matrix to produce the reduced dataset. sklearn.random_projection has some implementations of this. If the size and distribution of the projection matrix is appropriate, then the pairwise distances between points is almost preserved in the projected space.
Feature Hashing: Take a hash of the feature values, take the modulus $m$ where $m$ is the desired dimensionality. Hash collisions are dealt with by taking the sum of values that collide. You can think of it as shuffling the order of the features, splitting the data matrix into a series of vertical slices, and adding them all together elementwise. For sparse data, collisions are pretty rare. sklearn.feature_extraction.FeatureHasher is an implementation that (I believe) only works on string inputs; I think it's usually used for bag-of-words text style data.
