Analysis of SparseHash: An efficient embedding of set-similarity via sparse projections.

• Development of an efficient implementation of SparseHash. • Development of an approximated Fast SparseHash. • Theoretical analysis of SparseHash, in terms of preservation of Jaccard coefficient. • Theoretical analysis of SparseHash, in terms of Hamming distance in LSH • Numerical experiments on real datasets (text documents and metagenome clustering). 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. [ABSTRACT FROM AUTHOR]