We propose a robust framework for clustering data. In practice, data obtained from real measurement devices can be incomplete, corrupted by gross errors, or not correspond to any assumed model. We show that, by properly harnessing the intrinsic low-dimensional structure of the data, these kinds of practical problems can be dealt with in a uniform fashion. In particular, we propose two robust segmentation algorithms: an algebraic method for data from multiple quadratic manifolds, and an information-theoretic approach for data from multiple linear subspaces. Our techniques draw from many diverse areas, including lossy data compression, sparse representation, algebraic geometry, and robust statistics. We verify the efficacy of our algorithms by applying them to the segmentation of tracked image features of objects in a dynamic scene under the affine and perspective camera models, and the segmentation of a natural image into regions with homogeneous texture. We benchmark the performance of our methods on many publicly available notion and imagery datasets. Our results are on par with state-of-the-art results, in many cases exceeding them. Finally, we explore potential extensions and improvements to our techniques as well as new applications. |