The Information-Theoretic Requirements of Subspace Clustering with Missing Data

@InProceedings{pmlr-v48-pimentel-alarcon16,
  title = 	 {The Information-Theoretic Requirements of Subspace Clustering with Missing Data},
  author = 	 {Pimentel-Alarcon, Daniel and Nowak, Robert},
  booktitle = 	 {Proceedings of The 33rd International Conference on Machine Learning},
  pages = 	 {802--810},
  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/pimentel-alarcon16.pdf},
  url = 	 {https://proceedings.mlr.press/v48/pimentel-alarcon16.html},
  abstract = 	 {Subspace clustering with missing data (SCMD) is a useful tool for analyzing incomplete datasets. Let d be the ambient dimension, and r the dimension of the subspaces. Existing theory shows that Nk = O(r d) columns per subspace are necessary for SCMD, and Nk =O(min d^(log d), d^(r+1) ) are sufficient. We close this gap, showing that Nk =O(r d) is also sufficient. To do this we derive deterministic sampling conditions for SCMD, which give precise information theoretic requirements and determine sampling regimes. These results explain the performance of SCMD algorithms from the literature. Finally, we give a practical algorithm to certify the output of any SCMD method deterministically.}
}