2018/04/26 by Ping Li, Li, Ping · 1 citation
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Machine Learning (cs.LG) #Methodology (stat.ME) #Random Matrices and Applications #Statistical Methods and Inference #cs.IR #cs.LG #stat.ME
paper · pdf · doi:10.48550/arxiv.1805.00533
arxiv created 2018/04/26 · openalex publication_date 2018/04/26 · arxiv updated 2018/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 = ∑i=1D ui ri, and y = ∑i=1D vi ri, where ri∼ N(0,1) iid. The "collision probability" is Pr(sgn(x)=sgn(y)) = 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 E(y- 1x≥ 0 + y+ 1x<0) and its normalized version. The recommended estimator almost matches the accuracy of the (computationally expensive) maximum likelihood estimator. At high similarity (ρ→1), the asymptotic variance of recommended estimator is only (4)/(3π) ≈ 0.4 of the estimator for sign-sign projections. At small k and high similarity, the improvement would be even much more substantial.