![[International Conference on Machine Learning Logo]](/image.pl?url=http%3a%2f%2fproceedings.mlr.press%2fv48%2fassets%2fimages%2flogo-pmlr.svg&f=jpg&w=240)
[edit]
Online Low-Rank Subspace Clustering by Basis Dictionary Pursuit
Jie Shen, Ping Li, Huan XuProceedings 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 - CPAPERTI - Online Low-Rank Subspace Clustering by Basis Dictionary PursuitAU - Jie ShenAU - Ping LiAU - Huan XuBT - Proceedings of The 33rd International Conference on Machine LearningDA - 2016/06/11ED - Maria Florina BalcanED - Kilian Q. WeinbergerID - pmlr-v48-shen16PB - PMLRDP - Proceedings of Machine Learning ResearchVL - 48SP - 622EP - 631L1 - http://proceedings.mlr.press/v48/shen16.pdfUR - https://proceedings.mlr.press/v48/shen16.htmlAB - 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, inProceedings of Machine Learning Research 48:622-631 Available from https://proceedings.mlr.press/v48/shen16.html.