Analysis of SparseHash: an efficient embedding of set-similarity via sparse projections
This work provides an efficient method for set-similarity estimation, which is useful for tasks involving sparse data, but it is incremental as it builds on existing random projection and hashing techniques.
The authors tackled the problem of efficiently embedding set-similarity metrics like the Jaccard coefficient by theoretically proving that SparseHash, a class of sparse random projections, preserves this coefficient for sparse signals, and they demonstrated its performance with numerical experiments on synthetic and real datasets.
Embeddings provide compact representations of signals in order to perform efficient inference in a wide variety of tasks. In particular, random projections are common tools to construct Euclidean distance-preserving embeddings, while hashing techniques are extensively used to embed set-similarity metrics, such as the Jaccard coefficient. In this letter, we theoretically prove that a class of random projections based on sparse matrices, called SparseHash, can preserve the Jaccard coefficient between the supports of sparse signals, which can be used to estimate set similarities. Moreover, besides the analysis, we provide an efficient implementation and we test the performance in several numerical experiments, both on synthetic and real datasets.