Filtrated Algebraic Subspace Clustering.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 122891708 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Filtrated Algebraic Subspace Clustering. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Tsakiris%2C+Manolis+C%2E%22">Tsakiris, Manolis C.</searchLink><relatesTo>1</relatesTo><i> m.tsakiris@jhu.edu</i><br /><searchLink fieldCode="AR" term="%22Vidal%2C+René%22">Vidal, René</searchLink><relatesTo>1</relatesTo><i> rvidal@jhu.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Imaging+Sciences%22">SIAM Journal on Imaging Sciences</searchLink>. 2017, Vol. 10 Issue 1, p372-415. 44p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Subspaces+%28Mathematics%29%22">Subspaces (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Cluster+analysis+%28Statistics%29%22">Cluster analysis (Statistics)</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Multiple+correspondence+analysis+%28Statistics%29%22">Multiple correspondence analysis (Statistics)</searchLink><br /><searchLink fieldCode="DE" term="%22Transversal+lines%22">Transversal lines</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=122891708 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/16M1083451 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 44 StartPage: 372 Subjects: – SubjectFull: Subspaces (Mathematics) Type: general – SubjectFull: Cluster analysis (Statistics) Type: general – SubjectFull: Polynomials Type: general – SubjectFull: Multiple correspondence analysis (Statistics) Type: general – SubjectFull: Transversal lines Type: general Titles: – TitleFull: Filtrated Algebraic Subspace Clustering. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Tsakiris, Manolis C. – PersonEntity: Name: NameFull: Vidal, René IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 01 Text: 2017 Type: published Y: 2017 Identifiers: – Type: issn-print Value: 19364954 Numbering: – Type: volume Value: 10 – Type: issue Value: 1 Titles: – TitleFull: SIAM Journal on Imaging Sciences Type: main |
| ResultId | 1 |
