Quantized Random Projections And Non-linear Estimation Of Cosine Similarity

Ping Li, Michael Mitzenmacher, Martin Slawski. Neural Information Processing Systems 2016

[Paper]    
Independent NEURIPS Quantisation

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.

Similar Work