A Caltech Library Service

Approximate Nearest Subspace Search with Applications to Pattern Recognition

Basri, Ronen and Hassner, Tal and Zelnik-Manor, Lihi (2007) Approximate Nearest Subspace Search with Applications to Pattern Recognition. In: 2007 IEEE Conference on Computer Vision and Pattern Recognition. IEEE , Piscataway, NJ. ISBN 1-4244-1179-3.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Linear and affine subspaces are commonly used to describe appearance of objects under different lighting, viewpoint, articulation, and identity. A natural problem arising from their use is - given a query image portion represented as a point in some high dimensional space - find a subspace near to the query. This paper presents an efficient solution to the approximate nearest subspace problem for both linear and affine subspaces. Our method is based on a simple reduction to the problem of nearest point search, and can thus employ tree based search or locality sensitive hashing to find a near subspace. Further speedup may be achieved by using random projections to lower the dimensionality of the problem. We provide theoretical proofs of correctness and error bounds of our construction and demonstrate its capabilities on synthetic and real data. Our experiments demonstrate that an approximate nearest subspace can be located significantly faster than the exact nearest subspace, while at the same time it can find better matches compared to a similar search on points, in the presence of variations due to viewpoint, lighting etc.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2007 IEEE. R.B and T.H. were supported in part by the A.M.N. Fund for the promotion of science, culture and arts in Israel and by the European Community grant IST-2002-506766 Aim@Shape. The vision group at the Weizmann Institute is supported in part by the Moross Foundation. L.Z.-M. was supported by ONR grant N00014-06-1-0734 and NSF grant CMS-0428075. Author names are ordered alphabetically due to equal contribution.
Funding AgencyGrant Number
A.M.N. Fund For The Promotion Of Science Culture And Arts In IsraelUNSPECIFIED
European CommunityIST-2002-506766
Moross FoundationUNSPECIFIED
Office of Naval Research (ONR)N00014-06-1-0734
Record Number:CaltechAUTHORS:20170424-173541345
Persistent URL:
Official Citation:R. Basri, T. Hassner and L. Zelnik-Manor, "Approximate Nearest Subspace Search with Applications to Pattern Recognition," 2007 IEEE Conference on Computer Vision and Pattern Recognition, Minneapolis, MN, 2007, pp. 1-8. doi: 10.1109/CVPR.2007.383201
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:76887
Deposited By: Kristin Buxton
Deposited On:25 Apr 2017 02:55
Last Modified:15 Nov 2021 17:03

Repository Staff Only: item control page