Title: Deterministic and Probabilistic Conditions for Finite Completability of Low-rank Multi-View Data,
Abstract: We consider the multi-view data completion problem, i.e., to complete a
matrix $\mathbf{U}=[\mathbf{U}_1|\mathbf{U}_2]$ where the ranks of
$\mathbf{U},\mathbf{U}_1$, and $\mathbf{U}_2$ are given. In particular, we
investigate the fundamental conditions on the sampling pattern, i.e., locations
of the sampled entries for finite completability of such a multi-view data
given the corresponding rank constraints. In contrast with the existing
analysis on Grassmannian manifold for a single-view matrix, i.e., conventional
matrix completion, we propose a geometric analysis on the manifold structure
for multi-view data to incorporate more than one rank constraint. We provide a
deterministic necessary and sufficient condition on the sampling pattern for
finite completability. We also give a probabilistic condition in terms of the
number of samples per column that guarantees finite completability with high
probability. Finally, using the developed tools, we derive the deterministic
and probabilistic guarantees for unique completability.