Name
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 stateof-the-art methods on several occasions, thus demonstrating the merit of the idea of filtrations. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1137/16M1083451 | SIAM JOURNAL ON IMAGING SCIENCES |
Keywords | Field | DocType |
generalized principal component analysis,subspace clustering,algebraic subspace clustering,subspace,arrangements,transversal subspaces,spectral clustering | Discrete mathematics,Combinatorics,Polynomial,Subspace topology,Correlation clustering,Linear subspace,Algebraic variety,Hyperplane,Orthogonal complement,Cluster analysis,Mathematics | Journal |
Volume | Issue | ISSN |
10 | 1 | 1936-4954 |
Citations | PageRank | References |
3 | 0.38 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manolis C. Tsakiris | 1 | 50 | 9.79 |
| rene victor valqui vidal | 2 | 5331 | 260.14 |