Bibliographic Details
| Title: |
Filtrated Algebraic Subspace Clustering. |
| Authors: |
Tsakiris, Manolis C.1 m.tsakiris@jhu.edu, Vidal, René1 rvidal@jhu.edu |
| Source: |
SIAM Journal on Imaging Sciences. 2017, Vol. 10 Issue 1, p372-415. 44p. |
| Subjects: |
Subspaces (Mathematics), Cluster analysis (Statistics), Polynomials, Multiple correspondence analysis (Statistics), Transversal lines |
| Abstract: |
Subspace clustering is the problem of clustering data that lie close to a union of linear subspaces. Existing algebraic subspace clustering methods are based on fitting the data with an algebraic variety and decomposing this variety into its constituent subspaces. Such methods are well suited to the case of a known number of subspaces of known and equal dimensions, where a single polynomial vanishing in the variety is sufficient to identify the subspaces. While subspaces of unknown and arbitrary dimensions can be handled using multiple vanishing polynomials, current approaches are not robust to corrupted data due to the difficulty of estimating the number of polynomials. As a consequence, the current practice is to use a single polynomial to fit the data with a union of hyperplanes containing the union of subspaces, an approach that works well only when the dimensions of the subspaces are high enough. In this paper, we propose a new algebraic subspace clustering algorithm, which can identify the subspace S passing through a point X by constructing a descending filtration of subspaces containing S. First, a single polynomial vanishing in the variety is identified and used to find a hyperplane containing S. After intersecting this hyperplane with the variety to obtain a subvariety, a new polynomial vanishing in the subvariety is found, and so on, until no nontrivial vanishing polynomial exists. In this case, our algorithm identifies S as the intersection of the hyperplanes identified thus far. By repeating this procedure for other points, our algorithm eventually identifies all the subspaces. Alternatively, by constructing a filtration at each data point and comparing any two filtrations using a suitable affinity, we propose a spectral version of our algebraic procedure based on spectral clustering, which is suitable for computations with noisy data. We show by experiments on synthetic and real data that the proposed algorithm outperforms state-of-the-art methods on several occasions, thus demonstrating the merit of the idea of filtrations. [ABSTRACT FROM AUTHOR] |
|
Copyright of SIAM Journal on Imaging Sciences is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
