  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.
