Sparse Projections for High-Dimensional Binary Codes

This paper addresses the problem of learning long bi-nary codes from high-dimensional data. We observe that two key challenges arise while learning and using long binary codes: (1) lack of an effective regularizer for the learned high-dimensional mapping and (2) high computa-tional cost for computing long codes. In this paper, we overcome both these problems by introducing a sparsity encouraging regularizer that reduces the effective number of parameters involved in the learned projection operator. This regularizer not only reduces overfitting but, due to the sparse nature of the projection matrix, also leads to a dra-matic reduction in the computational cost. To evaluate the effectiveness of our method, we analyze its performance on the problems of nearest neighbour search, image retrieval and image classification. Experiments on a number of chal-lenging datasets show that our method leads to better accu-racy than dense projections (ITQ [11] and LSH [16]) with the same code lengths, and meanwhile is over an order of magnitude faster. Furthermore, our method is also more ac-curate and faster than other recently proposed methods for speeding up high-dimensional binary encoding. 1