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, Technical Report CCIT #699 , Department of
Electrical Engineering, Technion, June 2008.
Click here
for the PDF
(883kb)
Click here
for the 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
| 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% |
Speaker recognition results
| Method |
Run-time |
Correct |
| ANS (Our result) |
4.6 sec. |
100% |
| Exact subspace search (with preprocessing) |
44.5 sec. |
100% |
| Exact subspace search (without
preprocessing) |
232 sec. |
100% |