Deterministic and Probabilistic Conditions for Finite Completability of Low-rank Multi-View Data
This work addresses the problem of completing low-rank multi-view data for researchers in matrix completion and machine learning, offering incremental improvements by extending analysis from single-view to multi-view settings.
The paper tackles the multi-view data completion problem by determining conditions on the sampling pattern for finite completability given rank constraints, providing deterministic necessary and sufficient conditions and probabilistic guarantees with high probability.
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.