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)

Abstract

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
PublisherSpringer
Pages802-817
Number of pages16
ISBN (Electronic)9783319464756
ISBN (Print)9783319464749
DOIs
Publication statusPublished - 2016
Externally publishedYes
EventEuropean Conference on Computer Vision 2016 - Amsterdam, Netherlands
Duration: 11 Oct 201614 Oct 2016
Conference number: 14th
http://www.eccv2016.org/
https://link.springer.com/book/10.1007/978-3-319-46448-0 (Proceedings)

Publication series

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

Conference

ConferenceEuropean Conference on Computer Vision 2016
Abbreviated titleECCV 2016
CountryNetherlands
CityAmsterdam
Period11/10/1614/10/16
Internet address

Keywords

  • Augmented Lagrangian
  • Semidefinite programming
  • Two-step hashing

Cite this