Binary hashing with semidefinite relaxation and augmented Lagrangian

Thanh-Toan Do, Anh-Dzung Doan, Duc-Thanh Nguyen, Ngai-Man Cheung

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

7 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationComputer Vision - ECCV 2016
Subtitle of host publication14th European Conference Amsterdam, The Netherlands, October 11–14, 2016 Proceedings, Part II
EditorsBastian Leibe, Jiri Matas, Nicu Sebe, Max Welling
Place of PublicationCham Switzerland
Number of pages16
ISBN (Electronic)9783319464756
ISBN (Print)9783319464749
Publication statusPublished - 2016
Externally publishedYes
EventEuropean Conference on Computer Vision 2016 - Amsterdam, Netherlands
Duration: 11 Oct 201614 Oct 2016
Conference number: 14th (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceEuropean Conference on Computer Vision 2016
Abbreviated titleECCV 2016
Internet address


  • Augmented Lagrangian
  • Semidefinite programming
  • Two-step hashing

Cite this