SoS-RSC: A Sum-of-Squares Polynomial Approach to Robustifying Subspace
Clustering Algorithms?
Abstract
This paper addresses the problem of subspace clustering in the presence of outliers. Typically, this scenario is
handled through a regularized optimization, whose computational complexity scales polynomially with the size of the
data. Further, the regularization terms need to be manually tuned to achieve optimal performance. To circumvent these difficulties, in this paper we propose an outlier
removal algorithm based on evaluating a suitable sum-ofsquares polynomial, computed directly from the data. This
algorithm only requires performing two singular value decompositions of fixed size, and provides certificates on the
probability of misclassifying outliers as inliers