The information-theoretic requirements of subspace clustering with missing data
Daniel Pimentel-Alarcón, Robert D. Nowak · International Conference on Machine Learning · 2016
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(rd) columns per subspace are necessary for SCMD, and Nk = O(min{dlog d, dr+1}) are sufficient. We close this gap, showing that Nk = O(rd) 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.