Skip to yearly menu bar Skip to main content


Quantized Random Projections and Non-Linear Estimation of Cosine Similarity

Ping Li · Michael Mitzenmacher · Martin Slawski

Area 5+6+7+8 #158

Keywords: [ Stochastic Methods ] [ (Other) Probabilistic Models and Methods ]

Abstract: Random projections constitute a simple, yet effective technique for dimensionality reduction with applications in learning and search problems. In the present paper, we consider the problem of estimating cosine similarities when the projected data undergo scalar quantization to $b$ bits. We here argue that the maximum likelihood estimator (MLE) is a principled approach to deal with the non-linearity resulting from quantization, and subsequently study its computational and statistical properties. A specific focus is on the on the trade-off between bit depth and the number of projections given a fixed budget of bits for storage or transmission. Along the way, we also touch upon the existence of a qualitative counterpart to the Johnson-Lindenstrauss lemma in the presence of quantization.

Live content is unavailable. Log in and register to view live content