Binary hashing with semidefinite relaxation and augmented Lagrangian

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

doi:10.1007/978-3-319-46475-6_49

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 proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	Computer Vision - ECCV 2016
Subtitle of host publication	14th European Conference Amsterdam, The Netherlands, October 11–14, 2016 Proceedings, Part II
Editors	Bastian Leibe, Jiri Matas, Nicu Sebe, Max Welling
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	802-817
Number of pages	16
ISBN (Electronic)	9783319464756
ISBN (Print)	9783319464749
DOIs	https://doi.org/10.1007/978-3-319-46475-6_49
Publication status	Published - 2016
Externally published	Yes
Event	European Conference on Computer Vision 2016 - Amsterdam, Netherlands Duration: 11 Oct 2016 → 14 Oct 2016 Conference number: 14th http://www.eccv2016.org/ https://link.springer.com/book/10.1007/978-3-319-46448-0 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9906
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	European Conference on Computer Vision 2016
Abbreviated title	ECCV 2016
Country	Netherlands
City	Amsterdam
Period	11/10/16 → 14/10/16
Internet address	http://www.eccv2016.org/ https://link.springer.com/book/10.1007/978-3-319-46448-0 (Proceedings)

Keywords

Augmented Lagrangian
Semidefinite programming
Two-step hashing

Access to Document

10.1007/978-3-319-46475-6_49

Link to publication in Scopus

Cite this

Do, T-T., Doan, A-D., Nguyen, D-T., & Cheung, N-M. (2016). Binary hashing with semidefinite relaxation and augmented Lagrangian. In B. Leibe, J. Matas, N. Sebe, & M. Welling (Eds.), Computer Vision - ECCV 2016: 14th European Conference Amsterdam, The Netherlands, October 11–14, 2016 Proceedings, Part II (pp. 802-817). (Lecture Notes in Computer Science; Vol. 9906 ). Springer. https://doi.org/10.1007/978-3-319-46475-6_49

Do, Thanh-Toan ; Doan, Anh-Dzung ; Nguyen, Duc-Thanh ; Cheung, Ngai-Man. / Binary hashing with semidefinite relaxation and augmented Lagrangian. Computer Vision - ECCV 2016: 14th European Conference Amsterdam, The Netherlands, October 11–14, 2016 Proceedings, Part II. editor / Bastian Leibe ; Jiri Matas ; Nicu Sebe ; Max Welling. Cham Switzerland : Springer, 2016. pp. 802-817 (Lecture Notes in Computer Science).

@inproceedings{99d9a51138a845c49aff66275f1c1a5a,

title = "Binary hashing with semidefinite relaxation and augmented Lagrangian",

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.",

keywords = "Augmented Lagrangian, Semidefinite programming, Two-step hashing",

author = "Thanh-Toan Do and Anh-Dzung Doan and Duc-Thanh Nguyen and Ngai-Man Cheung",

year = "2016",

doi = "10.1007/978-3-319-46475-6_49",

language = "English",

isbn = "9783319464749",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "802--817",

editor = "Bastian Leibe and Jiri Matas and Nicu Sebe and Max Welling",

booktitle = "Computer Vision - ECCV 2016",

note = "European Conference on Computer Vision 2016, ECCV 2016 ; Conference date: 11-10-2016 Through 14-10-2016",

url = "http://www.eccv2016.org/, https://link.springer.com/book/10.1007/978-3-319-46448-0",

}

Do, T-T, Doan, A-D, Nguyen, D-T & Cheung, N-M 2016, Binary hashing with semidefinite relaxation and augmented Lagrangian. in B Leibe, J Matas, N Sebe & M Welling (eds), Computer Vision - ECCV 2016: 14th European Conference Amsterdam, The Netherlands, October 11–14, 2016 Proceedings, Part II. Lecture Notes in Computer Science, vol. 9906 , Springer, Cham Switzerland, pp. 802-817, European Conference on Computer Vision 2016, Amsterdam, Netherlands, 11/10/16. https://doi.org/10.1007/978-3-319-46475-6_49

Binary hashing with semidefinite relaxation and augmented Lagrangian. / Do, Thanh-Toan; Doan, Anh-Dzung; Nguyen, Duc-Thanh; Cheung, Ngai-Man.

Computer Vision - ECCV 2016: 14th European Conference Amsterdam, The Netherlands, October 11–14, 2016 Proceedings, Part II. ed. / Bastian Leibe; Jiri Matas; Nicu Sebe; Max Welling. Cham Switzerland : Springer, 2016. p. 802-817 (Lecture Notes in Computer Science; Vol. 9906 ).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Binary hashing with semidefinite relaxation and augmented Lagrangian

AU - Do, Thanh-Toan

AU - Doan, Anh-Dzung

AU - Nguyen, Duc-Thanh

AU - Cheung, Ngai-Man

N1 - Conference code: 14th

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Augmented Lagrangian

KW - Semidefinite programming

KW - Two-step hashing

UR - http://www.scopus.com/inward/record.url?scp=84990829313&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-46475-6_49

DO - 10.1007/978-3-319-46475-6_49

M3 - Conference Paper

AN - SCOPUS:84990829313

SN - 9783319464749

T3 - Lecture Notes in Computer Science

SP - 802

EP - 817

BT - Computer Vision - ECCV 2016

A2 - Leibe, Bastian

A2 - Matas, Jiri

A2 - Sebe, Nicu

A2 - Welling, Max

PB - Springer

CY - Cham Switzerland

T2 - European Conference on Computer Vision 2016

Y2 - 11 October 2016 through 14 October 2016

ER -

Do T-T, Doan A-D, Nguyen D-T, Cheung N-M. Binary hashing with semidefinite relaxation and augmented Lagrangian. In Leibe B, Matas J, Sebe N, Welling M, editors, Computer Vision - ECCV 2016: 14th European Conference Amsterdam, The Netherlands, October 11–14, 2016 Proceedings, Part II. Cham Switzerland: Springer. 2016. p. 802-817. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-46475-6_49