Nonnegative sparse locality preserving hashing

It is a NP-hard problem to optimize the objective function of hash-based similarity search algorithms, such as Spectral Hashing and Self-Taught Hashing. To make the problem solvable, existing methods have relaxed the constraints on hash codes from binary values (discrete) to real values (continuous). Then eigenvalue decomposition was employed to achieve the relaxed real solution. The main problem is that the signs of the relaxed continuous solution are mixed. Such results may deviate severely from the true solution, which has lead to significant semantic loss. Moreover, eigenvalue decomposition confronts singularity problem when the dimension of the data is larger than the sample size. To address these problems, we propose a novel method named Nonnegative Sparse Locality Preserving Hashing (NSLPH). Nonnegative and sparse constraints are imposed for a more accurate solution which preserves semantic information well. Then, we have applied nonnegative quadratic programming and multiplicative updating to solve the optimization problem, which successfully avoids the singularity problem of the eigenvalue decomposition. The extensive experiments presented in this paper demonstrate that the proposed approach outperforms the state-of-the-art algorithms.