Abstract algebraic-geometric subspace clustering

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.