Quantized Random Projections and Non-Linear Estimation of Cosine Similarity
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.
NIPS 2016 Review of Paper ID 1404 “Quantized Random Projections and Non-Linear Estimation of Cosine Similarity”  This manuscript studies the problem of estimating cosine similarities when the projections are quantized to an arbitrary number of bits. Previous work has examined random projections with full precision (i.e. real-valued projections) and random projections that have been quantized to a single bit (i.e. binary-valued responses). This paper focuses on the middle ground. In particular, they examine a maximum likelihood estimator- presumably of cosine similarity under the quantization non-linearity--the trade-off between bit depth vs. the number of projections for storage or transmission (i.e. compression).   
The topic is of potential interest, but the authors wrote this manuscript with a specialized audience in mind. I am a non-specialist. As a consequence, I am not in a good position to evaluate the merits or the importance of the work to the authors’ academic community. However, I am in a position to evaluate the writing and the presentation of the submitted manuscript. It is clear that the manuscript would benefit from more thorough and methodical writing. Figures and figure captions are not carefully explained; it is often not clear whether the data presented in the figures buttress the claims and conclusions made by the authors. Sometimes, parameters are used that are never defined. In general, while the statement of the problem is clear and the mathematical development is largely clear and easy to follow, the numerical results presented by the authors are very difficult to make sense of.     Line 61: “for its first resp. second derivative.”  What is the first resp second derivative? Typo?  Line 129: “resp.”  resp.?   Line 131: “The assumption that the norms are known is reasonable since  1) information about the norms is lost because of quantization (a total loss occurs for b = 1 ) and 2) it  is not hard to satisfy in practice as they can be computed by one linear scan during data collection.”  Confusing, possibly incoherent sentence. How can it be reasonable to assume that the norms are known if information about the norms is lost.   Figure 3 Caption: What do the number in the first subplot’s legend indicate?   Line 268; “We perform 100 resp. 20 independent replications for synthetic resp. real data”  What does ‘resp.’ mean? The authors use it repeatedly in the manuscript. I do not know what it means and I could not decipher either from context or a google search what the authors intend it to mean.   Line 279: “Some of these findings  are reflected in Figures 4 and 5. We refer to the supplement for additional figures.”  Which findings? I could not figure out what the figures showed. The authors assert that their results can be summarized by the fact that many bit quantization is superior to one bit quantization. This seems like a sensible conclusion, but it is not clear how Figure 4 and 5 show that. Consider figure 5. First, the y-axis has a different scale for each subplot, so comparisons between b=2 and b=4 are not easy in the farm or rcv1 datasets. This is non-standard and should be rectified. Second, if one does take the time to compare the numbers for the MLE estimator (black curve), the numbers are nearly identical for both datasets. That is, it is not at all clear from the figure that a larger number of bits (2 vs 4) indeed yields better retrieval of the K nearest neighbors. It would also be nice to know whether the 0.92 fraction retrieved in the farm dataset is considered ‘good performance’.   Line 290: “For SVM classification, we  consider logarithmically spaced grids between 10^3  and 10^3  for the parameter C”  The SVM parameter C is never described or explained.  Line 301: “there is empirical evidence that using three or a higher number potentially matches the performance achieved in the full precision case.”  Three or a higher number of what? Bits?  Appendix Figure 1: “(Re-scaled) Empirical MSE k _  (b_MLE􀀀__ )2  for (averaged over 104  i.i.d. data sets with k  = 100) compared to the inverse information.”  Nonsense first sentence of caption.  Appendix Figure 5: “ verage fraction of K  = 10 nearest neighbors retrieved vs. total # of bits (log2  scale) of our approach (MLE) relative to that based on the Hamming distance and the linear approach.”  Typos.