Data-Dependent Sparsity for Subspace Clustering

Bo Xin, Yizhou Wang, Wen Gao, David Wipf
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:251-260, 2017.

Abstract

Subspace clustering is the process of assign- ing subspace memberships to a set of un- labeled data points assumed to have been drawn from the union of an unknown number of low-dimensional subspaces, possibly inter- laced with outliers or other data corruptions. By exploiting the fact that each inlier point has a sparse representation with respect to a dic- tionary formed by all the other points, an $\ell$1 regularized sparse subspace clustering (SSC) method has recently shown state-of-the-art ro- bustness and practical extensibility in a vari- ety of applications. But there remain impor- tant lingering weaknesses. In particular, the $\ell$1 norm solution is highly sensitive, often in a detrimental direction, to the very types of data structures that motivate interest in subspace clustering to begin with, sometimes leading to poor segmentation accuracy. However, as an alternative source of sparsity, we argue that a certain data-dependent, non-convex penalty function can compensate for dictionary struc- ture in a way that is especially germane to sub- space clustering problems. For example, we demonstrate that this proposal displays a form of invariance to feature-space transformations and affine translations that commonly disrupt existing methods, and moreover, in important settings we reveal that its performance quality is lower bounded by the $\ell$1 solution. Finally, we provide empirical comparisons on popu- lar benchmarks that corroborate our theoreti- cal findings and demonstrate superior perfor- mance when compared to recent state-of-the- art models.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-xin17a, title = {Data-Dependent Sparsity for Subspace Clustering}, author = {Xin, Bo and Wang, Yizhou and Gao, Wen and Wipf, David}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {251--260}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/xin17a/xin17a.pdf}, url = {https://proceedings.mlr.press/r15/xin17a.html}, abstract = {Subspace clustering is the process of assign- ing subspace memberships to a set of un- labeled data points assumed to have been drawn from the union of an unknown number of low-dimensional subspaces, possibly inter- laced with outliers or other data corruptions. By exploiting the fact that each inlier point has a sparse representation with respect to a dic- tionary formed by all the other points, an $\ell$1 regularized sparse subspace clustering (SSC) method has recently shown state-of-the-art ro- bustness and practical extensibility in a vari- ety of applications. But there remain impor- tant lingering weaknesses. In particular, the $\ell$1 norm solution is highly sensitive, often in a detrimental direction, to the very types of data structures that motivate interest in subspace clustering to begin with, sometimes leading to poor segmentation accuracy. However, as an alternative source of sparsity, we argue that a certain data-dependent, non-convex penalty function can compensate for dictionary struc- ture in a way that is especially germane to sub- space clustering problems. For example, we demonstrate that this proposal displays a form of invariance to feature-space transformations and affine translations that commonly disrupt existing methods, and moreover, in important settings we reveal that its performance quality is lower bounded by the $\ell$1 solution. Finally, we provide empirical comparisons on popu- lar benchmarks that corroborate our theoreti- cal findings and demonstrate superior perfor- mance when compared to recent state-of-the- art models.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Data-Dependent Sparsity for Subspace Clustering %A Bo Xin %A Yizhou Wang %A Wen Gao %A David Wipf %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-xin17a %I PMLR %P 251--260 %U https://proceedings.mlr.press/r15/xin17a.html %V R15 %X Subspace clustering is the process of assign- ing subspace memberships to a set of un- labeled data points assumed to have been drawn from the union of an unknown number of low-dimensional subspaces, possibly inter- laced with outliers or other data corruptions. By exploiting the fact that each inlier point has a sparse representation with respect to a dic- tionary formed by all the other points, an $\ell$1 regularized sparse subspace clustering (SSC) method has recently shown state-of-the-art ro- bustness and practical extensibility in a vari- ety of applications. But there remain impor- tant lingering weaknesses. In particular, the $\ell$1 norm solution is highly sensitive, often in a detrimental direction, to the very types of data structures that motivate interest in subspace clustering to begin with, sometimes leading to poor segmentation accuracy. However, as an alternative source of sparsity, we argue that a certain data-dependent, non-convex penalty function can compensate for dictionary struc- ture in a way that is especially germane to sub- space clustering problems. For example, we demonstrate that this proposal displays a form of invariance to feature-space transformations and affine translations that commonly disrupt existing methods, and moreover, in important settings we reveal that its performance quality is lower bounded by the $\ell$1 solution. Finally, we provide empirical comparisons on popu- lar benchmarks that corroborate our theoreti- cal findings and demonstrate superior perfor- mance when compared to recent state-of-the- art models. %Z Reissued by PMLR on 04 October 2026.
APA
Xin, B., Wang, Y., Gao, W. & Wipf, D.. (2017). Data-Dependent Sparsity for Subspace Clustering. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:251-260 Available from https://proceedings.mlr.press/r15/xin17a.html. Reissued by PMLR on 04 October 2026.

Related Material