Sparse Subspace Clustering with Missing Entries

Congyuan Yang, Daniel Robinson, Rene Vidal
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:2463-2472, 2015.

Abstract

We consider the problem of clustering incomplete data drawn from a union of subspaces. Classical subspace clustering methods are not applicable to this problem because the data are incomplete, while classical low-rank matrix completion methods may not be applicable because data in multiple subspaces may not be low rank. This paper proposes and evaluates two new approaches for subspace clustering and completion. The first one generalizes the sparse subspace clustering algorithm so that it can obtain a sparse representation of the data using only the observed entries. The second one estimates a suitable kernel matrix by assuming a random model for the missing entries and obtains the sparse representation from this kernel. Experiments on synthetic and real data show the advantages and disadvantages of the proposed methods, which all outperform the natural approach (low-rank matrix completion followed by sparse subspace clustering) when the data matrix is high-rank or the percentage of missing entries is large.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-yangf15, title = {Sparse Subspace Clustering with Missing Entries}, author = {Yang, Congyuan and Robinson, Daniel and Vidal, Rene}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {2463--2472}, 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/yangf15.pdf}, url = {https://proceedings.mlr.press/v37/yangf15.html}, abstract = {We consider the problem of clustering incomplete data drawn from a union of subspaces. Classical subspace clustering methods are not applicable to this problem because the data are incomplete, while classical low-rank matrix completion methods may not be applicable because data in multiple subspaces may not be low rank. This paper proposes and evaluates two new approaches for subspace clustering and completion. The first one generalizes the sparse subspace clustering algorithm so that it can obtain a sparse representation of the data using only the observed entries. The second one estimates a suitable kernel matrix by assuming a random model for the missing entries and obtains the sparse representation from this kernel. Experiments on synthetic and real data show the advantages and disadvantages of the proposed methods, which all outperform the natural approach (low-rank matrix completion followed by sparse subspace clustering) when the data matrix is high-rank or the percentage of missing entries is large.} }
Endnote
%0 Conference Paper %T Sparse Subspace Clustering with Missing Entries %A Congyuan Yang %A Daniel Robinson %A Rene Vidal %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-yangf15 %I PMLR %P 2463--2472 %U https://proceedings.mlr.press/v37/yangf15.html %V 37 %X We consider the problem of clustering incomplete data drawn from a union of subspaces. Classical subspace clustering methods are not applicable to this problem because the data are incomplete, while classical low-rank matrix completion methods may not be applicable because data in multiple subspaces may not be low rank. This paper proposes and evaluates two new approaches for subspace clustering and completion. The first one generalizes the sparse subspace clustering algorithm so that it can obtain a sparse representation of the data using only the observed entries. The second one estimates a suitable kernel matrix by assuming a random model for the missing entries and obtains the sparse representation from this kernel. Experiments on synthetic and real data show the advantages and disadvantages of the proposed methods, which all outperform the natural approach (low-rank matrix completion followed by sparse subspace clustering) when the data matrix is high-rank or the percentage of missing entries is large.
RIS
TY - CPAPER TI - Sparse Subspace Clustering with Missing Entries AU - Congyuan Yang AU - Daniel Robinson AU - Rene Vidal BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-yangf15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 2463 EP - 2472 L1 - http://proceedings.mlr.press/v37/yangf15.pdf UR - https://proceedings.mlr.press/v37/yangf15.html AB - We consider the problem of clustering incomplete data drawn from a union of subspaces. Classical subspace clustering methods are not applicable to this problem because the data are incomplete, while classical low-rank matrix completion methods may not be applicable because data in multiple subspaces may not be low rank. This paper proposes and evaluates two new approaches for subspace clustering and completion. The first one generalizes the sparse subspace clustering algorithm so that it can obtain a sparse representation of the data using only the observed entries. The second one estimates a suitable kernel matrix by assuming a random model for the missing entries and obtains the sparse representation from this kernel. Experiments on synthetic and real data show the advantages and disadvantages of the proposed methods, which all outperform the natural approach (low-rank matrix completion followed by sparse subspace clustering) when the data matrix is high-rank or the percentage of missing entries is large. ER -
APA
Yang, C., Robinson, D. & Vidal, R.. (2015). Sparse Subspace Clustering with Missing Entries. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:2463-2472 Available from https://proceedings.mlr.press/v37/yangf15.html.

Related Material