On deterministic conditions for subspace clustering under missing data

In this paper we consider the problem of data clustering under the union of subspaces (UOS) model [1], [2], when each data vector is sampled in an element-wise manner. This is referred to as the case of missing data. In other words we are looking to harvest a union of subspaces structure from the data, when the data is missing. Such a problem has been recently considered in a number of papers [3], [4], [5], [6]. This setting has implications to data completion under the union of subspaces model in contrast to the single subspace model that has been prevalent in the matrix completion literature. In contrast to statistical analysis in [3], [4], [5], this paper uses a variant of the sparse subspace clustering (SSC) algorithm [2] to give sufficient deterministic conditions for accurate subspace clustering under missing data. In contrast to [6], which does not provide any specific conditions for success of SSC under missing data, in this paper we provide implications of the deterministic conditions for several specific cases of sampling. Further through extensive simulations we demonstrate for the first time that accurate clustering under missing data does not imply accurate subspace clustering and completion thereby indicating the natural order of hardness of these problems under missing data.