A General Framework for Approximate Nearest Subspace Search
Published in 2nd IEEE International Workshop on Subspace Methods at the IEEE International Conference on Computer Vision (ICCV), Kyoto, 2009
Recommended citation: Ronen Basri, Tal Hassner, and Lihi Zelnik-Manor*. A General Framework for Approximate Nearest Subspace Search. 2nd IEEE International Workshop on Subspace Methods at the IEEE International Conference on Computer Vision (ICCV), Kyoto, 2009.
Older tech-report Reference: R. Basri, T.Hassner and L. Zelnik-Manor, A General Framework for Approximate Nearest Subspace Search, Technical Report CCIT #699 , Department of Electrical Engineering, Technion, June 2008.
Subspaces offer convenient means of representing information in many Pattern Recognition, Machine Vision, and Statistical Learning applications. Contrary to the growing popularity of subspace representations, the problem of efficiently searching through large subspace databases has received little attention in the past. In this paper we present a general solution to the Approximate Nearest Subspace search problem. Our solution uniformly handles cases where both query and database elements may differ in dimensionality, where the database contains subspaces of different dimensions, and where the queries themselves may be subspaces. To this end we present a simple mapping from subspaces to points, thus reducing the problem to the well studied Approximate Nearest Neighbor problem on points. We provide theoretical proofs of correctness and error bounds of our construction and demonstrate its performance on synthetic and real data. Our tests indicate that an approximate nearest subspace can be located significantly faster than the nearest subspace, with little loss of accuracy.
Please see paper for a full description of our experiments and more results.
Synthetic Data Tests
|Varying database size||Varying query dimension||Varying ambient space|
log-scale run times compared for an exact linear search, linear search with a preprocessed database and our ANS method with ANN epsilon=100. The following tests were performed. Varying number of database subspaces (database size): Database subspaces of dimension 30 embedded in a 60 dimensional space, tested with 1000 queries of dimension 10. Varying query dimension: Database contains 1000 subspaces with dimension 30, tested with 1000 queries. Varying ambient dimension: Database contains 1000 subspaces with dimension 30, tested with 1000 queries of dimension 10. The error rate for our method remained at an almost constant 0.01 in all three experiments, through all values tested.
Scene Classification Results
|ANS (Our result)||2.3 sec.||63%|
|Exact subspace search (with preprocessing)||13.8 sec.||63%|
|Exact nearest patch||135 sec||55%|