Locally linear hashing for extracting non-linear manifolds

Go Irie, Zhenguo Li, Xiaoming Wu, Shih Fu Chang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

73 Citations (Scopus)


Previous efforts in hashing intend to preserve data variance or pairwise affinity, but neither is adequate in capturing the manifold structures hidden in most visual data. In this paper, we tackle this problem by reconstructing the locally linear structures of manifolds in the binary Hamming space, which can be learned by locality-sensitive sparse coding. We cast the problem as a joint minimization of reconstruction error and quantization loss, and show that, despite its NP-hardness, a local optimum can be obtained efficiently via alternative optimization. Our method distinguishes itself from existing methods in its remarkable ability to extract the nearest neighbors of the query from the same manifold, instead of from the ambient space. On extensive experiments on various image benchmarks, our results improve previous state-of-the-art by 28-74% typically, and 627% on the Yale face data.
Original languageEnglish
Title of host publicationProceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
PublisherIEEE Computer Society
Number of pages8
ISBN (Electronic)9781479951178
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event27th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014 - Columbus, United States
Duration: 23 Jun 201428 Jun 2014


Conference27th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014
Country/TerritoryUnited States


  • hashing
  • local linearity
  • manifold
  • retrieval

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition

Cite this