Fast binary embedding via circulant downsampled matrix

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-d...

Full description

Saved in:
Bibliographic Details
Main Authors: Sung-Hsien Hsieh, Chun-Shien Lu, Soo-Chang Pei
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Binary codes
Circulant matrix
Compressed sensing
Computational efficiency
Dimensionality reduction
Distortion
Embedding
Linear matrix inequalities
Memory management
Random projection
Subsampling
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 M×M 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.
ISSN:2381-8549
DOI:10.1109/ICIP.2016.7532666