Faster Binary Embeddings for Preserving Euclidean Distances
Authors:
Preprint
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.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Fast Binary Embeddings with Gaussian Circulant Matrices: Improved BoundsDiscrete & Computational Geometry, 2018
- Flickr30k Entities: Collecting Region-to-Phrase Correspondences for Richer Image-to-Sentence ModelsInternational Journal of Computer Vision, 2016
- An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss TransformACM Transactions on Algorithms, 2013
- Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image RetrievalIEEE Transactions on Pattern Analysis and Machine Intelligence, 2012
- High-dimensional signature compression for large-scale image classification2011
- An optimal family of exponentially accurate one‐bit Sigma‐Delta quantization schemesCommunications on Pure and Applied Mathematics, 2011
- New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry PropertySIAM Journal on Mathematical Analysis, 2011
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010
- The Fast Johnson–Lindenstrauss Transform and Approximate Nearest NeighborsSIAM Journal on Computing, 2009
- On variants of the Johnson–Lindenstrauss lemmaRandom Structures & Algorithms, 2008