Scalable Solution for Approximate Nearest Subspace Search
This provides a scalable solution for applications requiring fast and accurate nearest subspace search, addressing a bottleneck in large-scale problems.
The paper tackles the problem of approximate nearest subspace search (ANSS) for large-scale datasets with many subspaces and high dimensionality, proposing a method that represents subspaces with multiple points, which resulted in a 7.3 times speed improvement over the previous state-of-the-art without accuracy loss.
Finding the nearest subspace is a fundamental problem and influential to many applications. In particular, a scalable solution that is fast and accurate for a large problem has a great impact. The existing methods for the problem are, however, useless in a large-scale problem with a large number of subspaces and high dimensionality of the feature space. A cause is that they are designed based on the traditional idea to represent a subspace by a single point. In this paper, we propose a scalable solution for the approximate nearest subspace search (ANSS) problem. Intuitively, the proposed method represents a subspace by multiple points unlike the existing methods. This makes a large-scale ANSS problem tractable. In the experiment with 3036 subspaces in the 1024-dimensional space, we confirmed that the proposed method was 7.3 times faster than the previous state-of-the-art without loss of accuracy.