Efficient point-to-subspace query in ℓ 1 with application to robust face recognition

Ju Sun, Yuqian Zhang, John Wright

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

1 Scopus citations


Motivated by vision tasks such as robust face and object recognition, we consider the following general problem: given a collection of low-dimensional linear subspaces in a high-dimensional ambient (image) space, and a query point (image), efficiently determine the nearest subspace to the query in ℓ 1 distance. We show in theory this problem can be solved with a simple two-stage algorithm: (1) random Cauchy projection of query and subspaces into low-dimensional spaces followed by efficient distance evaluation (ℓ 1 regression); (2) getting back to the high-dimensional space with very few candidates and performing exhaustive search. We present preliminary experiments on robust face recognition to corroborate our theory.

Original languageEnglish (US)
Title of host publicationComputer Vision, ECCV 2012 - 12th European Conference on Computer Vision, Proceedings
Number of pages14
EditionPART 4
StatePublished - Oct 30 2012
Externally publishedYes
Event12th European Conference on Computer Vision, ECCV 2012 - Florence, Italy
Duration: Oct 7 2012Oct 13 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 4
Volume7575 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th European Conference on Computer Vision, ECCV 2012


  • Cauchy projection
  • face recognition
  • nearest subspace search
  • subspace modeling
  • ℓ point-to-subspace distance


Dive into the research topics of 'Efficient point-to-subspace query in ℓ <sup>1</sup> with application to robust face recognition'. Together they form a unique fingerprint.

Cite this