Graph Connectivity in Noisy Sparse Subspace Clustering

Yining Wang, Yu-Xiang Wang, Aarti Singh
; Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:538-546, 2016.

Abstract

Subspace clustering is the problem of clustering data points into a union of low-dimensional linear/affine subspaces. It is the mathematical abstraction of many important problems in computer vision, image processing and machine learning. A line of recent work [4, 19, 24, 20] provided strong theoretical guarantee for sparse subspace cluster- ing [4], the state-of-the-art algorithm for sub- space clustering, on both noiseless and noisy data sets. It was shown that under mild conditions, with high probability no two points from different subspaces are clustered together. Such guarantee, however, is not sufficient for the clustering to be correct, due to the notorious “graph connectivity problem” [15]. In this paper, we investigate the graph connectivity problem for noisy sparse sub-space clustering and show that a simple post-processing procedure is capable of delivering consistent clustering under certain “general position” or “restricted eigenvalue” assumptions. We also show that our condition is almost tight with adversarial noise perturbation by constructing a counter-example. These results provide the first exact clustering guarantee of noisy SSC for subspaces of dimension greater then 3.

Cite this Paper


BibTeX
@InProceedings{pmlr-v51-wang16b, title = {Graph Connectivity in Noisy Sparse Subspace Clustering}, author = {Yining Wang and Yu-Xiang Wang and Aarti Singh}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {538--546}, year = {2016}, editor = {Arthur Gretton and Christian C. Robert}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/wang16b.pdf}, url = {http://proceedings.mlr.press/v51/wang16b.html}, abstract = {Subspace clustering is the problem of clustering data points into a union of low-dimensional linear/affine subspaces. It is the mathematical abstraction of many important problems in computer vision, image processing and machine learning. A line of recent work [4, 19, 24, 20] provided strong theoretical guarantee for sparse subspace cluster- ing [4], the state-of-the-art algorithm for sub- space clustering, on both noiseless and noisy data sets. It was shown that under mild conditions, with high probability no two points from different subspaces are clustered together. Such guarantee, however, is not sufficient for the clustering to be correct, due to the notorious “graph connectivity problem” [15]. In this paper, we investigate the graph connectivity problem for noisy sparse sub-space clustering and show that a simple post-processing procedure is capable of delivering consistent clustering under certain “general position” or “restricted eigenvalue” assumptions. We also show that our condition is almost tight with adversarial noise perturbation by constructing a counter-example. These results provide the first exact clustering guarantee of noisy SSC for subspaces of dimension greater then 3.} }
Endnote
%0 Conference Paper %T Graph Connectivity in Noisy Sparse Subspace Clustering %A Yining Wang %A Yu-Xiang Wang %A Aarti Singh %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-wang16b %I PMLR %J Proceedings of Machine Learning Research %P 538--546 %U http://proceedings.mlr.press %V 51 %W PMLR %X Subspace clustering is the problem of clustering data points into a union of low-dimensional linear/affine subspaces. It is the mathematical abstraction of many important problems in computer vision, image processing and machine learning. A line of recent work [4, 19, 24, 20] provided strong theoretical guarantee for sparse subspace cluster- ing [4], the state-of-the-art algorithm for sub- space clustering, on both noiseless and noisy data sets. It was shown that under mild conditions, with high probability no two points from different subspaces are clustered together. Such guarantee, however, is not sufficient for the clustering to be correct, due to the notorious “graph connectivity problem” [15]. In this paper, we investigate the graph connectivity problem for noisy sparse sub-space clustering and show that a simple post-processing procedure is capable of delivering consistent clustering under certain “general position” or “restricted eigenvalue” assumptions. We also show that our condition is almost tight with adversarial noise perturbation by constructing a counter-example. These results provide the first exact clustering guarantee of noisy SSC for subspaces of dimension greater then 3.
RIS
TY - CPAPER TI - Graph Connectivity in Noisy Sparse Subspace Clustering AU - Yining Wang AU - Yu-Xiang Wang AU - Aarti Singh BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics PY - 2016/05/02 DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-wang16b PB - PMLR SP - 538 DP - PMLR EP - 546 L1 - http://proceedings.mlr.press/v51/wang16b.pdf UR - http://proceedings.mlr.press/v51/wang16b.html AB - Subspace clustering is the problem of clustering data points into a union of low-dimensional linear/affine subspaces. It is the mathematical abstraction of many important problems in computer vision, image processing and machine learning. A line of recent work [4, 19, 24, 20] provided strong theoretical guarantee for sparse subspace cluster- ing [4], the state-of-the-art algorithm for sub- space clustering, on both noiseless and noisy data sets. It was shown that under mild conditions, with high probability no two points from different subspaces are clustered together. Such guarantee, however, is not sufficient for the clustering to be correct, due to the notorious “graph connectivity problem” [15]. In this paper, we investigate the graph connectivity problem for noisy sparse sub-space clustering and show that a simple post-processing procedure is capable of delivering consistent clustering under certain “general position” or “restricted eigenvalue” assumptions. We also show that our condition is almost tight with adversarial noise perturbation by constructing a counter-example. These results provide the first exact clustering guarantee of noisy SSC for subspaces of dimension greater then 3. ER -
APA
Wang, Y., Wang, Y. & Singh, A.. (2016). Graph Connectivity in Noisy Sparse Subspace Clustering. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in PMLR 51:538-546

Related Material