Information-theoretic Bounds on Matrix Completion under Union of Subspaces Model

Matrix completion refers to the recovery of a low-rank matrix from a (small) subset of its entries or a (small) number of linear combinations of its entries [1-4]. In essence, the methods are aimed at recovering the column/row subspaces from limited measurements. Even the sketching methods [8] aim to find the best column (or row) subspace of a matrix. However, in many practical applications, the columns of the data matrix can belong to different low rank subspaces (or affine subspaces) [5-7, 9].