# Coding for Random Projections

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2013.

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

- [OPORP: One Permutation + One Random Projection](https://mlsanity.com/paper/2302.03505/) (2023)
- [One Loss for Quantization: Deep Hashing with Discrete Wasserstein Distributional Matching](https://mlsanity.com/paper/2205.15721/) (2022)
- [Quantization Algorithms for Random Fourier Features](https://mlsanity.com/paper/2102.13079/) (2021)
- [Differential Privacy with Random Projections and Sign Random Projections](https://mlsanity.com/paper/2306.01751/) (2023)
- [Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling](https://mlsanity.com/paper/2306.07674/) (2023)
- [QLESS: A Quantized Approach for Data Valuation and Selection in Large Language Model Fine-Tuning](https://mlsanity.com/paper/2502.01703/) (2025)
- [Tree-based Text-Vision BERT for Video Search in Baidu Video Advertising](https://mlsanity.com/paper/2209.08759/) (2022)
- [Ternary and Binary Quantization for Improved Classification](https://mlsanity.com/paper/2203.16798/) (2022)

## Abstract (arXiv)

The method of random projections has become very popular for large-scale applications in statistical learning, information retrieval, bio-informatics and other applications. Using a well-designed coding scheme for the projected data, which determines the number of bits needed for each projected value and how to allocate these bits, can significantly improve the effectiveness of the algorithm, in storage cost as well as computational speed. In this paper, we study a number of simple coding schemes, focusing on the task of similarity estimation and on an application to training linear classifiers. We demonstrate that uniform quantization outperforms the standard existing influential method (Datar et. al. 2004). Indeed, we argue that in many cases coding with just a small number of bits suffices. Furthermore, we also develop a non-uniform 2-bit coding scheme that generally performs well in practice, as confirmed by our experiments on training linear support vector machines (SVM).