Faster Binary Embeddings for Preserving Euclidean Distances

Jinjie Zhang, Rayan Saab

Abstract

We propose a fast, distance-preserving, binary embedding algorithm to transform a high-dimensional dataset $\mathcal{T}\subseteq\mathbb{R}^n$ into binary sequences in the cube $\{\pm 1\}^m$. When $\mathcal{T}$ consists of well-spread (i.e., non-sparse) vectors, our embedding method applies a stable noise-shaping quantization scheme to $Ax$ where $A\in\mathbb{R}^{m\times n}$ is a sparse Gaussian random matrix. This contrasts with most binary embedding methods, which usually use $x\mapsto \mathrm{sign}(Ax)$ for the embedding. Moreover, we show that Euclidean distances among the elements of $\mathcal{T}$ are approximated by the $\ell_1$ norm on the images of $\{\pm 1\}^m$ under a fast linear transformation. This again contrasts with standard methods, where the Hamming distance is used instead. Our method is both fast and memory efficient, with time complexity $O(m)$ and space complexity $O(m)$. Further, we prove that the method is accurate and its associated error is comparable to that of a continuous valued Johnson-Lindenstrauss embedding plus a quantization error that admits a polynomial decay as the embedding dimension $m$ increases. Thus the length of the binary codes required to achieve a desired accuracy is quite small, and we show it can even be compressed further without compromising the accuracy. To illustrate our results, we test the proposed method on natural images and show that it achieves strong performance.

Introduction

In the era of big data, reducing the dimensionality of massive datasets is crucial for efficient storage and computation. While the Johnson-Lindenstrauss (JL) Lemma provides a framework for projecting data into lower-dimensional spaces while preserving pairwise distances, storing continuous-valued vectors remains memory-intensive. Binary embedding addresses this by mapping vectors to the binary cube $\{ \pm 1 \}^m$.

Standard binary embedding methods typically use a random matrix multiplication followed by a sign function ($x \to \text{sign}(Ax)$). However, these methods suffer from magnitude loss, slow error decay relative to the number of bits $m$, and significant computational costs—often $O(n \log n)$ per data point. This paper introduces a novel algorithm that achieves $O(m)$ time complexity for "well-spread" data while providing superior accuracy through noise-shaping quantization.

Proposed Methodology

The proposed approach consists of two primary components: a sparse embedding process and a specialized recovery mechanism.

Sparse Matrices and Noise-Shaping

Instead of dense matrices, the method utilizes a sparse Gaussian random matrix $A$. To mitigate information loss during quantization, the standard memoryless sign function is replaced with Sigma-Delta ($\Sigma\Delta$) quantization. This "noise-shaping" scheme pushes quantization errors into higher frequencies, allowing them to be filtered out during distance estimation.

The Condensation Operator

Distance recovery is performed using a sparse "condensation operator" $V$ applied to the binary strings, followed by an $\ell_1$ norm calculation. This operator acts as a low-pass filter, removing the shaped quantization noise to reveal the preserved Euclidean distance. This differs significantly from traditional methods that rely on Hamming distance and only capture angular information.

Handling Data Sparsity

The $O(m)$ speedup is optimized for "well-spread" data where information is distributed across coordinates. For sparse or "spiky" data, a Walsh-Hadamard transform pre-processing step is employed, bringing the complexity to $O(n \log n)$, which remains competitive with state-of-the-art fast JL transforms.

Key Results

The method was evaluated on high-dimensional image datasets, including the Yelp Open Dataset, ImageNet, and CIFAR-10.

Distance MAPE vs. embedding dimension $m$ for different methods and quantization orders.

As shown in the experimental results, the Mean Absolute Percentage Error (MAPE) decays rapidly as the embedding dimension $m$ increases. Notably, higher-order quantizers ($r=2$) converge to the performance of unquantized embeddings significantly faster than the standard $r=1$ (greedy) approach. The method achieves $O(m)$ time and space complexity for well-spread data, outperforming baselines like Circulant or Bilinear embeddings. Furthermore, the binary codes are highly bit-efficient; for instance, achieving less than 10% error with only approximately 0.023 bits per pixel on image data.

Discussion and Conclusion

The proposed method offers a significant advancement in fast binary embeddings by preserving magnitude and achieving faster error decay. While the $O(m)$ speedup is contingent on the "well-spread" assumption, natural images typically satisfy this condition. The use of sparse matrices and noise-shaping quantization allows for highly compact binary codes without compromising distance preservation. Future work may explore parallelization of the iterative $\Sigma\Delta$ quantization process on specialized hardware like FPGAs or ASICs to further enhance performance in real-time applications.

Summary updated

Abstract

We propose a fast, distance-preserving, binary embedding algorithm to transform a high-dimensional dataset $\mathcal{T}\subseteq\mathbb{R}^n$ into binary sequences in the cube $\{\pm 1\}^m$. When $\mathcal{T}$ consists of well-spread (i.e., non-sparse) vectors, our embedding method applies a stable noise-shaping quantization scheme to $A x$ where $A\in\mathbb{R}^{m\times n}$ is a sparse Gaussian random matrix. This contrasts with most binary embedding methods, which usually use $x\mapsto \mathrm{sign}(Ax)$ for the embedding. Moreover, we show that Euclidean distances among the elements of $\mathcal{T}$ are approximated by the $\ell_1$ norm on the images of $\{\pm 1\}^m$ under a fast linear transformation. This again contrasts with standard methods, where the Hamming distance is used instead. Our method is both fast and memory efficient, with time complexity $O(m)$ and space complexity $O(m)$. Further, we prove that the method is accurate and its associated error is comparable to that of a continuous valued Johnson-Lindenstrauss embedding plus a quantization error that admits a polynomial decay as the embedding dimension $m$ increases. Thus the length of the binary codes required to achieve a desired accuracy is quite small, and we show it can even be compressed further without compromising the accuracy. To illustrate our results, we test the proposed method on natural images and show that it achieves strong performance.
BibTeX
@inproceedings{zhang2021faster,
  author = {Jinjie Zhang and Rayan Saab},
  title = {{Faster Binary Embeddings for Preserving Euclidean Distances}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=YCXrx6rRCXO},
}
Figure