Subspace Clustering With Priors via Sparse Quadratically Constrained Quadratic Programming

Yongfang Cheng, Yin Wang, Mario Sznaier, Octavia Camps; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016, pp. 5204-5212

Abstract


This paper considers the problem of recovering a subspace arrangement from noisy samples, potentially corrupted with outliers. Our main result shows that this problem can be formulated as a convex semi-definite optimization problem subject to an additional rank constrain that involves only a very small number of variables. This is established by first reducing the problem to a (generically non-convex) quadratically constrained quadratic problem and then using its special sparse structure to find conditions guaranteeing that a suitably built convex relaxation is indeed exact. When combined with the commonly used nuclear norm relaxation for rank, the results above lead to computationally efficient algorithms with optimality guarantees. A salient feature of the proposed approach is its ability to incorporate existing a-priori information about the noise, co-ocurrences, and percentage of outliers. These results are illustrated with several examples where the proposed algorithm is shown to outperform existing approaches.

Related Material


[pdf]
[bibtex]
@InProceedings{Cheng_2016_CVPR,
author = {Cheng, Yongfang and Wang, Yin and Sznaier, Mario and Camps, Octavia},
title = {Subspace Clustering With Priors via Sparse Quadratically Constrained Quadratic Programming},
booktitle = {Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2016}
}