Sparse Dimensionality Reduction Revisited

The sparse Johnson-Lindenstrauss transform is one of the central techniques in dimensionality reduction. It supports embedding a set of n points in ℝd into m=O(varepsilon-2 lg n) dimensions while preserving all pairwise distances to within 1 ± varepsilon. Each input point x is embedded to Ax, where A is an m × d matrix having s non-zeros per column, allowing for an embedding time of O(s |x|0). Since the sparsity of A governs the embedding time, much work has gone into improving the sparsity s. The current state-of-the-art by Kane and Nelson (JACM'14) shows that s = O(varepsilon -1 lg n) suffices. This is almost matched by a lower bound of s = Omega(varepsilon -1 lg n/lg(1/varepsilon)) by Nelson and Nguyen (STOC'13). Previous work thus suggests that we have near-optimal embeddings. In this work, we revisit sparse embeddings and identify a loophole in the lower bound. Concretely, it requires d ≥ n, which in many applications is unrealistic. We exploit this loophole to give a sparser embedding when d = o(n), achieving s = O(varepsilon-1(lg n/lg(1/varepsilon)+lg2/3n lg1/3 d)). We also complement our analysis by strengthening the lower bound of Nelson and Nguyen to hold also when d ll n, thereby matching the first term in our new sparsity upper bound. Finally, we also improve the sparsity of the best oblivious subspace embeddings for optimal embedding dimensionality.