Supervised discrete hashing

Recently, learning based hashing techniques have at-tracted broad research interests because they can support efficient storage and retrieval for high-dimensional data such as images, videos, documents, etc. However, a ma-jor difficulty of learning to hash lies in handling the dis-crete constraints imposed on the pursued hash codes, which typically makes hash optimizations very challenging (NP-hard in general). In this work, we propose a new super-vised hashing framework, where the learning objective is to generate the optimal binary hash codes for linear clas-sification. By introducing an auxiliary variable, we refor-mulate the objective such that it can be solved substantially efficiently by employing a regularization algorithm. One of the key steps in this algorithm is to solve a regulariza-tion sub-problem associated with the NP-hard binary op-timization. We show that the sub-problem admits an ana-lytical solution via cyclic coordinate descent. As such, a high-quality discrete solution can eventually be obtained in an efficient computing manner, therefore enabling to tack-le massive datasets. We evaluate the proposed approach, dubbed Supervised Discrete Hashing (SDH), on four large image datasets and demonstrate its superiority to the state-of-the-art hashing methods in large-scale image retrieval. 1