Fast Binary Embedding via Circulant Downsampled Matrix -- A Data-Independent Approach

2016/01/24 by Hsieh, Sung-Hsien, Lu, Chun-Shien, Pei, Soo-Chang
#Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.1601.06342

Abstract

Binary embedding of high-dimensional data aims to produce low-dimensional binary codes while preserving discriminative power. State-of-the-art methods often suffer from high computation and storage costs. We present a simple and fast embedding scheme by first downsampling N-dimensional data into M-dimensional data and then multiplying the data with an MxM circulant matrix. Our method requires O(N +M log M) computation and O(N) storage costs. We prove if data have sparsity, our scheme can achieve similarity-preserving well. Experiments further demonstrate that though our method is cost-effective and fast, it still achieves comparable performance in image applications.

Related

• Circulant Binary Embedding
• On Binary Embedding using Circulant Matrices
• Faster Binary Embeddings for Preserving Euclidean Distances
• Projection Bank: From High-dimensional Data to Medium-length Binary Codes
• Fast binary embeddings with Gaussian circulant matrices: improved bounds