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 capabilities on synthetic and real data. Our experiments
indicate that an approximate nearest subspace can be located significantly faster
than the nearest subspace, with little loss of accuracy.
Reference: R. Basri, T.Hassner
and L. 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, Sept 2009.
Click here for the
PDF (833kb)
Click here for the
BibTex
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.
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
|
Method |
Run-time |
Correct |
|
ANS (Our result) |
2.3 sec. |
63% |
|
Exact subspace search (with preprocessing) |
13.8 sec. |
63% |
|
Exact nearest patch |
135 sec |
55% |