Filtrated algebraic subspace clustering
From MaRDI portal
Abstract: Subspace clustering is the problem of clustering data that lie close to a union of linear subspaces. In the abstract form of the problem, where no noise or other corruptions are present, the data are assumed to lie in general position inside the algebraic variety of a union of subspaces, and the objective is to decompose the variety into its constituent subspaces. Prior algebraic-geometric approaches to this problem require the subspaces to be of equal dimension, or the number of subspaces to be known. Subspaces of arbitrary dimensions can still be recovered in closed form, in terms of all homogeneous polynomials of degree that vanish on their union, when an upper bound m on the number of the subspaces is given. In this paper, we propose an alternative, provably correct, algorithm for addressing a union of at most arbitrary-dimensional subspaces, based on the idea of descending filtrations of subspace arrangements. Our algorithm uses the gradient of a vanishing polynomial at a point in the variety to find a hyperplane containing the subspace S passing through that point. By intersecting the variety with this hyperplane, we obtain a subvariety that contains S, and recursively applying the procedure until no non-trivial vanishing polynomial exists, our algorithm eventually identifies S. By repeating this procedure for other points, our algorithm eventually identifies all the subspaces by returning a basis for their orthogonal complement. Finally, we develop a variant of the abstract algorithm, 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.
Recommendations
Cites work
- \(k\)-plane clustering
- A geometric analysis of subspace clustering with outliers
- A preconditioned hybrid SVD method for accurately computing singular triplets of large matrices
- A sharp bound for the Castelnuovo-Mumford regularity of subspace arrangements.
- Castelnuovo-Mumford regularity of products of ideals
- Computing singular values of large matrices with an inverse-free preconditioned Krylov subspace method
- Estimation of Subspace Arrangements with Applications in Modeling and Segmenting Mixed Data
- Filtrated algebraic subspace clustering
- Generalized principal component analysis
- Hilbert series of subspace arrangements
- scientific article; zbMATH DE number 43569 (Why is no real title available?)
- scientific article; zbMATH DE number 3572315 (Why is no real title available?)
- scientific article; zbMATH DE number 704831 (Why is no real title available?)
- scientific article; zbMATH DE number 2165490 (Why is no real title available?)
- scientific article; zbMATH DE number 6665535 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Hybrid Systems: Computation and Control
- Iterative computation of the smallest singular value and the corresponding singular vectors of a matrix.
- Multiple View Geometry in Computer Vision
- Nearest \(q\)-flat to \(m\) points
- Robust subspace clustering
- Two-view multibody structure from motion
Cited in
(6)
This page was built for publication: Filtrated algebraic subspace clustering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5266379)
