Understanding Sparse JL for Feature Hashing

Publication date 8 March 2019

Has companion code repository https://github.com/mjagadeesan/sparsejl-featurehashing

Abstract: Feature hashing and other random projection schemes are commonly used to reduce the dimensionality of feature vectors. The goal is to efficiently project a high-dimensional feature vector living in

m a t h b b R^{n}

into a much lower-dimensional space

m a t h b b R^{m}

, while approximately preserving Euclidean norm. These schemes can be constructed using sparse random projections, for example using a sparse Johnson-Lindenstrauss (JL) transform. A line of work introduced by Weinberger et. al (ICML '09) analyzes the accuracy of sparse JL with sparsity 1 on feature vectors with small

e l l_{i} n f t y

-to-

e l l_{2}

norm ratio. Recently, Freksen, Kamma, and Larsen (NeurIPS '18) closed this line of work by proving a tight tradeoff between

e l l_{i} n f t y

-to-

e l l_{2}

norm ratio and accuracy for sparse JL with sparsity

1

. In this paper, we demonstrate the benefits of using sparsity

s

greater than

1

in sparse JL on feature vectors. Our main result is a tight tradeoff between

e l l_{i} n f t y

-to-

e l l_{2}

norm ratio and accuracy for a general sparsity

s

, that significantly generalizes the result of Freksen et. al. Our result theoretically demonstrates that sparse JL with

s > 1

can have significantly better norm-preservation properties on feature vectors than sparse JL with

s = 1

; we also empirically demonstrate this finding.

This page was built for publication: Understanding Sparse JL for Feature Hashing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315296)