Timezone: »

 
Poster
Quantized Random Projections and Non-Linear Estimation of Cosine Similarity
Ping Li · Michael Mitzenmacher · Martin Slawski

Mon Dec 05 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #158
in Monday Posters »
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.
Keywords: (Other) Probabilistic Models and Methods · Stochastic Methods
[ PDF] 

Author Information

Ping Li (Baidu Research USA)
Michael Mitzenmacher (Harvard University)
Martin Slawski (George Mason University)

More from the Same Authors