Academic Commons


Efficient Point-to-Subspace Query in ℓ1 with Application to Robust Face Recognition

Sun, Ju; Zhang, Yuqian; Wright, John N.

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.


  • thumnail for 978-3-642-33765-9_30.pdf 978-3-642-33765-9_30.pdf application/x-pdf 558 KB Download File

Also Published In

Computer Vision -- ECCV 2012: 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 2012: Proceedings, Part IV

More About This Work

Academic Units
Electrical Engineering
Lecture Notes in Computer Science, 7575
Published Here
October 16, 2012
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.