A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data

Yining Wang, Yu-Xiang Wang, Aarti Singh
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1422-1431, 2015.

Abstract

Subspace clustering groups data into several lowrank subspaces. In this paper, we propose a theoretical framework to analyze a popular optimization-based algorithm, Sparse Subspace Clustering (SSC), when the data dimension is compressed via some random projection algorithms. We show SSC provably succeeds if the random projection is a subspace embedding, which includes random Gaussian projection, uniform row sampling, FJLT, sketching, etc. Our analysis applies to the most general deterministic setting and is able to handle both adversarial and stochastic noise. It also results in the first algorithm for privacy-preserved subspace clustering.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-wange15, title = {A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data}, author = {Wang, Yining and Wang, Yu-Xiang and Singh, Aarti}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1422--1431}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/wange15.pdf}, url = {https://proceedings.mlr.press/v37/wange15.html}, abstract = {Subspace clustering groups data into several lowrank subspaces. In this paper, we propose a theoretical framework to analyze a popular optimization-based algorithm, Sparse Subspace Clustering (SSC), when the data dimension is compressed via some random projection algorithms. We show SSC provably succeeds if the random projection is a subspace embedding, which includes random Gaussian projection, uniform row sampling, FJLT, sketching, etc. Our analysis applies to the most general deterministic setting and is able to handle both adversarial and stochastic noise. It also results in the first algorithm for privacy-preserved subspace clustering.} }
Endnote
%0 Conference Paper %T A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data %A Yining Wang %A Yu-Xiang Wang %A Aarti Singh %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-wange15 %I PMLR %P 1422--1431 %U https://proceedings.mlr.press/v37/wange15.html %V 37 %X Subspace clustering groups data into several lowrank subspaces. In this paper, we propose a theoretical framework to analyze a popular optimization-based algorithm, Sparse Subspace Clustering (SSC), when the data dimension is compressed via some random projection algorithms. We show SSC provably succeeds if the random projection is a subspace embedding, which includes random Gaussian projection, uniform row sampling, FJLT, sketching, etc. Our analysis applies to the most general deterministic setting and is able to handle both adversarial and stochastic noise. It also results in the first algorithm for privacy-preserved subspace clustering.
RIS
TY - CPAPER TI - A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data AU - Yining Wang AU - Yu-Xiang Wang AU - Aarti Singh BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-wange15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1422 EP - 1431 L1 - http://proceedings.mlr.press/v37/wange15.pdf UR - https://proceedings.mlr.press/v37/wange15.html AB - Subspace clustering groups data into several lowrank subspaces. In this paper, we propose a theoretical framework to analyze a popular optimization-based algorithm, Sparse Subspace Clustering (SSC), when the data dimension is compressed via some random projection algorithms. We show SSC provably succeeds if the random projection is a subspace embedding, which includes random Gaussian projection, uniform row sampling, FJLT, sketching, etc. Our analysis applies to the most general deterministic setting and is able to handle both adversarial and stochastic noise. It also results in the first algorithm for privacy-preserved subspace clustering. ER -
APA
Wang, Y., Wang, Y. & Singh, A.. (2015). A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1422-1431 Available from https://proceedings.mlr.press/v37/wange15.html.

Related Material