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.

Abstract

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.

Download paper here

BibTeX

Some Results

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