Faster Binary Embeddings for Preserving Euclidean Distances

Jinjie Zhang, Rayan Saab

Overview

Researchers have developed a new binary embedding algorithm that transforms high-dimensional data into short binary codes while accurately preserving Euclidean distances. By combining sparse random matrices with "noise-shaping" quantization, the method achieves $O(m)$ time complexity for well-spread data—significantly faster than traditional methods—while providing theoretical error guarantees that improve rapidly as the code length increases.

The High-Dimensional Bottleneck

In the era of "Big Data," we often deal with vectors spanning thousands or millions of dimensions. Storing and comparing these vectors is computationally expensive and memory-intensive. Dimensionality reduction techniques, like the famous Johnson-Lindenstrauss (JL) Lemma, allow us to project data into lower-dimensional spaces while preserving distances, but the resulting vectors still consist of high-precision floating-point numbers.

Binary embeddings take this a step further by mapping data to a sequence of bits ($\{-1, 1\}^m$). This drastically reduces storage and allows for lightning-fast comparisons using bitwise operations. However, standard binary embedding methods—which usually just take the sign of a linear projection—suffer from two main flaws:

  1. Slow Error Decay: The approximation error improves very slowly as you add more bits.
  2. Information Loss: Taking the sign of a vector completely discards its magnitude; two vectors in the same direction but with different lengths become indistinguishable.

The authors aim to create a binary embedding that is both faster to compute and more accurate at recovering original Euclidean distances.

A Three-Step Embedding Pipeline

The paper introduces a novel pipeline for embedding a dataset $\mathcal{T} \subset \mathbb{R}^n$:

  1. Sparse Linear Projection: Instead of a dense matrix, the method uses a sparse Gaussian random matrix $A$. For "well-spread" data (where information is distributed across many coordinates, like in natural images), this reduces the projection cost to $O(m)$. If the data is sparse, they first apply a fast Walsh-Hadamard transform ($O(n \log n)$).
  2. Sigma-Delta ($\Sigma\Delta$) Quantization: Instead of the standard memoryless "sign" function, they use a stable noise-shaping scheme. This process "pushes" quantization error into higher frequencies. In simple terms, the quantizer "remembers" the error made on one bit and tries to compensate for it in the next.
  3. $\ell_1$ Distance Recovery: Unlike standard methods that use Hamming distance, this approach recovers distances by applying a "condensation operator" $V$ (a sparse matrix) to the binary codes and then calculating the $\ell_1$ norm: $d_{\tilde{V}}(q_x, q_y) = \|\tilde{V}(q_x - q_y)\|_1$.

Key Insights

  • Noise Shaping is Superior to Rounding: The core "aha moment" is that quantization isn't just about rounding; it's about where you put the error. By using $\Sigma\Delta$ quantization, the error decays polynomially with the number of bits ($m$), whereas standard rounding (MSQ) decays much slower.
  • Sparsity for Speed: The authors prove that if your data is "well-spread," you don't need a dense projection matrix. A very sparse matrix is sufficient to preserve the geometry, allowing the embedding to be computed in time proportional to the output size ($O(m)$) rather than the input size ($O(n)$).
  • Natural Images are "Well-Spread": A significant practical insight is that natural images naturally satisfy the "well-spread" condition. This means the $O(m)$ fast embedding can be used directly on image data without expensive pre-processing.

Empirical Performance and Results

The authors evaluated their method on several real-world image datasets, including Yelp Open Dataset, ImageNet, Flickr30k, and CIFAR-10. All images were converted to grayscale and resized to create high-dimensional vectors (e.g., 16,384 dimensions for $128 \times 128$ images).

  • Theoretical Accuracy: The error bound is shown to decay at a rate of $(m/p)^{-r+1/2}$, where $r$ is the order of the quantizer. This allows for very high accuracy with relatively short bitstrings.
  • Computational Efficiency: On well-spread data, the method achieves $O(m)$ time and space complexity. This is faster than Gaussian Toeplitz, Bilinear, or Circulant embeddings, which typically require $O(n \log n)$ or $O(n\sqrt{m})$.
  • Empirical Performance: In experiments on the Yelp dataset, the error (MAPE) dropped significantly as the number of bits $m$ increased, closely following the predicted theoretical decay.
Distance MAPE vs. embedding dimension $m$

For $m=4096$, the construction achieved less than 10% error while using only about 0.023 bits per pixel.

Limitations and Future Work

  • The "Well-Spread" Requirement: The $O(m)$ speedup is contingent on the data not being sparse. While natural images fit this, other types of data (like bag-of-words models) might require the $O(n \log n)$ pre-processing step, neutralizing some of the speed advantages.
  • Hardware Implementation: While the $\ell_1$ recovery is mathematically elegant, standard Hamming distance is natively supported by CPU instructions (POPCNT). Implementing the condensation operator $V$ and $\ell_1$ norm efficiently in hardware is a practical hurdle for real-time systems.
  • Parameter Sensitivity: The performance depends on choosing the right embedding dimension $p$ and quantization order $r$. The authors suggest these can be optimized empirically, but a more automated way to select these for arbitrary datasets would be beneficial.

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)$ on well-spread data. When the data is not well-spread, we show that the approach still works provided that data is transformed via a Walsh-Hadamard matrix, but now the cost is $O(n\log n)$ per data point. 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