# Improving LSH via Tensorized Random Projection

arXiv: https://arxiv.org/abs/2402.07189 · HTML: https://mlsanity.com/paper/2402.07189/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 11 Feb 2024.

## Builds on (most cited first, 11 of 11)

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Tensor Methods in Computer Vision and Deep Learning](https://mlsanity.com/paper/2107.03436/) (2021)
- [Introduction to Tensor Decompositions and their Applications in Machine Learning](https://mlsanity.com/paper/1711.10781/) (2017)
- [Extension of PCA to Higher Order Data Structures: An Introduction to Tensors, Tensor Decompositions, and Tensor PCA](https://mlsanity.com/paper/1803.00704/) (2018)
- [In Defense of MinHash Over SimHash](https://mlsanity.com/paper/1407.4416/) (2014)
- [Tensorized Random Projections](https://mlsanity.com/paper/2003.05101/) (2020)
- [Optimal Densification for Fast and Accurate Minwise Hashing](https://mlsanity.com/paper/1703.04664/) (2017)
- [Circulant Binary Embedding](https://mlsanity.com/paper/1405.3162/) (2014)
- [Predicting Multidimensional Data via Tensor Learning](https://mlsanity.com/paper/2002.04328/) (2020)
- [Rademacher Random Projections with Tensor Networks](https://mlsanity.com/paper/2110.13970/) (2021)

## Abstract (arXiv)

Locality sensitive hashing (LSH) is a fundamental algorithmic toolkit used by data scientists for approximate nearest neighbour search problems that have been used extensively in many large scale data processing applications such as near duplicate detection, nearest neighbour search, clustering, etc. In this work, we aim to propose faster and space efficient locality sensitive hash functions for Euclidean distance and cosine similarity for tensor data. Typically, the naive approach for obtaining LSH for tensor data involves first reshaping the tensor into vectors, followed by applying existing LSH methods for vector data E2LSH and SRP. However, this approach becomes impractical for higher order tensors because the size of the reshaped vector becomes exponential in the order of the tensor. Consequently, the size of LSH parameters increases exponentially. To address this problem, we suggest two methods for LSH for Euclidean distance and cosine similarity, namely CP-E2LSH, TT-E2LSH, and CP-SRP, TT-SRP, respectively, building on CP and tensor train (TT) decompositions techniques. Our approaches are space efficient and can be efficiently applied to low rank CP or TT tensors. We provide a rigorous theoretical analysis of our proposal on their correctness and efficacy.