Subspace Clustering with Ordered Weighted L1 Minimization

We consider the problem of clustering a collection of N unlabeled data points assumed to lie near a union of k lower dimensional planes. This assumption works in certain computer vision applications such as face recognition and image segmentation. Elhamifar and Vidal have proposed “Sparse Subspace Clustering (SSC)” algorithm to solve this problem which has also been theoretically analyzed by Candès and Soltanolkotabi. This algorithm basically solves l-1 minimization program for each data point. We consider an alternative algorithm which only solves k many convex optimizations to achieve the clustering. We do not know in advance how many subspaces there are nor do we have any information about their dimensions. Our motivation is a recent result by Figueiredo and Nowak where they employ “ordered weighted l-1 regularization (OWL)” in linear regression with strongly correlated variables. Given this power of OWL, we employ a similar technique for subspace clustering problem where we can assume apriori that the data points on the same subspace are highly correlated with each other when compared to other data points. We present experimental results to show the efficiency of the algorithm and also give preliminary theoretical results about its performance.