Binary Hashing with Semidefinite Relaxation and Augmented Lagrangian
This work addresses the problem of efficient similarity search in large-scale data retrieval for applications like image or text search, presenting incremental improvements to existing hashing methods.
The paper tackles the problem of learning binary codes for hashing by formulating it as a Binary Quadratic Problem and proposing two solution approaches: a semidefinite relaxation with theoretical guarantees and an augmented Lagrangian method that directly handles binary constraints. Experimental results on three benchmark datasets show that the methods perform competitively with state-of-the-art approaches.
This paper proposes two approaches for inferencing binary codes in two-step (supervised, unsupervised) hashing. We first introduce an unified formulation for both supervised and unsupervised hashing. Then, we cast the learning of one bit as a Binary Quadratic Problem (BQP). We propose two approaches to solve BQP. In the first approach, we relax BQP as a semidefinite programming problem which its global optimum can be achieved. We theoretically prove that the objective value of the binary solution achieved by this approach is well bounded. In the second approach, we propose an augmented Lagrangian based approach to solve BQP directly without relaxing the binary constraint. Experimental results on three benchmark datasets show that our proposed methods compare favorably with the state of the art.