# Sign-Full Random Projections

arXiv: https://arxiv.org/abs/1805.00533 · HTML: https://mlsanity.com/paper/1805.00533/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2018.

## Built on by (most cited first, 7 of 7)

- [BOAT: Bilateral Local Attention Vision Transformer](https://mlsanity.com/paper/2201.13027/) (2022)
- [OPORP: One Permutation + One Random Projection](https://mlsanity.com/paper/2302.03505/) (2023)
- [Differential Privacy with Random Projections and Sign Random Projections](https://mlsanity.com/paper/2306.01751/) (2023)
- [Tree-based Text-Vision BERT for Video Search in Baidu Video Advertising](https://mlsanity.com/paper/2209.08759/) (2022)
- [CoopHash: Cooperative Learning of Multipurpose Descriptor and Contrastive Pair Generator via Variational MCMC Teaching for Supervised Image Hashing](https://mlsanity.com/paper/2210.04288/) (2022)
- [Noisy ℓ0-Sparse Subspace Clustering on Dimensionality Reduced Data](https://mlsanity.com/paper/2206.11079/) (2022)
- [FERRET: Private Deep Learning Faster And Better Than DPSGD](https://mlsanity.com/paper/2506.05416/) (2025)

## Abstract (arXiv)

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.