Paper Info
Title
Abstract algebraic-geometric subspace clustering
Abstract
Subspace clustering is the problem of clustering data drawn from a union of linear subspaces. Prior algebraic-geometric approaches to this problem required the subspaces to be of equal dimension, or the number of subspaces to be known. While an algorithm addressing the general case of an unknown number of subspaces of possibly different dimensions had been proposed, a proof for its correctness had not been given. In this paper, we consider an abstract version of the subspace clustering problem, where one is given the algebraic variety of the union of subspaces rather than the data points. Our main contribution is to propose a provably correct algorithm for decomposing the algebraic variety into the constituent subspaces in the general case of an unknown number of subspaces of possibly different dimensions. Our algorithm uses the gradient of a vanishing polynomial at a point in the variety to find a hyperplane containing the subspace passing through that point. By intersecting the variety with this hyperplane and recursively applying the procedure, our algorithm eventually identifies the subspace containing that point. By repeating this procedure for other points, our algorithm eventually identifies all the subspaces and their dimensions.
Year
DOI
Venue
2014
10.1109/ACSSC.2014.7094674
Pacific Grove, CA
Keywords
Field
DocType
algebraic geometric codes,pattern clustering,polynomials,abstract algebraic-geometric subspace clustering problem,algebraic variety intersection,hyperplane,linear subspace,vanishing polynomial
Data point,Discrete mathematics,Combinatorics,Subspace topology,Polynomial,Computer science,Correctness,Linear subspace,Algebraic variety,Hyperplane,Cluster analysis
Conference
Volume
ISSN
Citations 
abs/1506.06289
1058-6393
3
PageRank 
References 
Authors
0.39
11
2
Name
Order
Citations
PageRank
Manolis C. Tsakiris1509.79
rene victor valqui vidal25331260.14