Fast subspace search via grassmannian based hashing

Xu Wang, Stefan Atev, John Wright, Gilad Lerman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations


The problem of efficiently deciding which of a database of models is most similar to a given input query arises throughout modern computer vision. Motivated by applications in recognition, image retrieval and optimization, there has been significant recent interest in the variant of this problem in which the database models are linear subspaces and the input is either a point or a subspace. Current approaches to this problem have poor scaling in high dimensions, and may not guarantee sub linear query complexity. We present a new approach to approximate nearest subspace search, based on a simple, new locality sensitive hash for subspaces. Our approach allows point-to-subspace query for a database of subspaces of arbitrary dimension d, in a time that depends sub linearly on the number of subspaces in the database. The query complexity of our algorithm is linear in the ambient dimension D, allowing it to be directly applied to high-dimensional imagery data. Numerical experiments on model problems in image repatching and automatic face recognition confirm the advantages of our algorithm in terms of both speed and accuracy.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE International Conference on Computer Vision, ICCV 2013
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Print)9781479928392
StatePublished - 2013
Event2013 14th IEEE International Conference on Computer Vision, ICCV 2013 - Sydney, NSW, Australia
Duration: Dec 1 2013Dec 8 2013

Publication series

NameProceedings of the IEEE International Conference on Computer Vision


Other2013 14th IEEE International Conference on Computer Vision, ICCV 2013
CitySydney, NSW


  • Grassmannian Based Hashing
  • Locality Sensitive Hashing
  • Subspace Search


Dive into the research topics of 'Fast subspace search via grassmannian based hashing'. Together they form a unique fingerprint.

Cite this