Sign-Full Random Projections

The method of 1-bit ("sign-sign") random projections has been a popular tool for efficient search and machine learning on large datasets. Given two D-dim data vectors u, v∈ℝD, one can generate x = sumi=1D ui ri, and y = sumi=1D vi ri, where ri~ N(0,1) iid. The "collision probability" is Prleft(sgn(x)=sgn(y)right) = 1-fraccos-1ρπ, where ρ = ρ(u,v) is the cosine similarity. We develop "sign-full" random projections by estimating ρ from (e.g.,) the expectation E(sgn(x)y)=√frac2π ρ, which can be further substantially improved by normalizing y. For nonnegative data, we recommend an interesting estimator based on Eleft(y_- 1x≥ 0 + y_+ 1x<0right) and its normalized version. The recommended estimator almost matches the accuracy of the (computationally expensive) maximum likelihood estimator. At high similarity (ρrightarrow1), the asymptotic variance of recommended estimator is only frac43π ≈ 0.4 of the estimator for sign-sign projections. At small k and high similarity, the improvement would be even much more substantial.