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

Ju Sun, Yuqian Zhang, and John Wright

Abstract. 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 ¹ 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 (¹ 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.

Keywords: ℓ1 point-to-subspace distance, nearest subspace search, Cauchy projection, face recognition, subspace modeling

LNCS 7575, p. 416 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012