Matrix completability analysis via graph kconnectivity
[edit]
Proceedings of the TwentyFirst International Conference on Artificial Intelligence and Statistics, PMLR 84:395403, 2018.
Abstract
The problem of lowrank matrix completion is continually attracting attention for its applicability to many realworld problems. Still, the large size, extreme sparsity, and nonuniformity of these matrices pose a challenge. In this paper, we make the observation that even when the observed matrix is too sparse for accurate completion, there may be portions of the data where completion is still possible. We propose the completeID algorithm, which exploits the nonuniformity of the observation, to analyze the completability of the input instead of blindly applying completion. Balancing statistical accuracy with computational efficiency, we relate completability to edgeconnectivity of the graph associated with the input partiallyobserved matrix. We develop the MaxKCD algorithm for finding maximally kedgeconnected components efficiently. Experiments across datasets from a variety of applications demonstrate not only the success of completeID but also the importance of completability analysis.
Related Material


