Online Low-Rank Subspace Clustering by Basis Dictionary Pursuit

Jie Shen, Ping Li, Huan Xu
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:622-631, 2016.

Abstract

Low-Rank Representation (LRR) has been a significant method for segmenting data that are generated from a union of subspaces. It is also known that solving LRR is challenging in terms of time complexity and memory footprint, in that the size of the nuclear norm regularized matrix is n-by-n (where n is the number of samples). In this paper, we thereby develop a novel online implementation of LRR that reduces the memory cost from O(n^2) to O(pd), with p being the ambient dimension and d being some estimated rank (d < p < n). We also establish the theoretical guarantee that the sequence of solutions produced by our algorithm converges to a stationary point of the expected loss function asymptotically. Extensive experiments on synthetic and realistic datasets further substantiate that our algorithm is fast, robust and memory efficient.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-shen16, title = {Online Low-Rank Subspace Clustering by Basis Dictionary Pursuit}, author = {Shen, Jie and Li, Ping and Xu, Huan}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {622--631}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/shen16.pdf}, url = {https://proceedings.mlr.press/v48/shen16.html}, abstract = {Low-Rank Representation (LRR) has been a significant method for segmenting data that are generated from a union of subspaces. It is also known that solving LRR is challenging in terms of time complexity and memory footprint, in that the size of the nuclear norm regularized matrix is n-by-n (where n is the number of samples). In this paper, we thereby develop a novel online implementation of LRR that reduces the memory cost from O(n^2) to O(pd), with p being the ambient dimension and d being some estimated rank (d < p < n). We also establish the theoretical guarantee that the sequence of solutions produced by our algorithm converges to a stationary point of the expected loss function asymptotically. Extensive experiments on synthetic and realistic datasets further substantiate that our algorithm is fast, robust and memory efficient.} }
Endnote
%0 Conference Paper %T Online Low-Rank Subspace Clustering by Basis Dictionary Pursuit %A Jie Shen %A Ping Li %A Huan Xu %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-shen16 %I PMLR %P 622--631 %U https://proceedings.mlr.press/v48/shen16.html %V 48 %X Low-Rank Representation (LRR) has been a significant method for segmenting data that are generated from a union of subspaces. It is also known that solving LRR is challenging in terms of time complexity and memory footprint, in that the size of the nuclear norm regularized matrix is n-by-n (where n is the number of samples). In this paper, we thereby develop a novel online implementation of LRR that reduces the memory cost from O(n^2) to O(pd), with p being the ambient dimension and d being some estimated rank (d < p < n). We also establish the theoretical guarantee that the sequence of solutions produced by our algorithm converges to a stationary point of the expected loss function asymptotically. Extensive experiments on synthetic and realistic datasets further substantiate that our algorithm is fast, robust and memory efficient.
RIS
TY - CPAPER TI - Online Low-Rank Subspace Clustering by Basis Dictionary Pursuit AU - Jie Shen AU - Ping Li AU - Huan Xu BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-shen16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 622 EP - 631 L1 - http://proceedings.mlr.press/v48/shen16.pdf UR - https://proceedings.mlr.press/v48/shen16.html AB - Low-Rank Representation (LRR) has been a significant method for segmenting data that are generated from a union of subspaces. It is also known that solving LRR is challenging in terms of time complexity and memory footprint, in that the size of the nuclear norm regularized matrix is n-by-n (where n is the number of samples). In this paper, we thereby develop a novel online implementation of LRR that reduces the memory cost from O(n^2) to O(pd), with p being the ambient dimension and d being some estimated rank (d < p < n). We also establish the theoretical guarantee that the sequence of solutions produced by our algorithm converges to a stationary point of the expected loss function asymptotically. Extensive experiments on synthetic and realistic datasets further substantiate that our algorithm is fast, robust and memory efficient. ER -
APA
Shen, J., Li, P. & Xu, H.. (2016). Online Low-Rank Subspace Clustering by Basis Dictionary Pursuit. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:622-631 Available from https://proceedings.mlr.press/v48/shen16.html.

Related Material