In masked low-rank approximation, one must find a low-rank matrix L which approximates a given matrix matrix A on just a subset of A's entries, corresponding to the 1s in a binary mask matrix W. Depending on how W is chosen, this proble captures matrix completion, factor analysis, low-rank plus diagonal decomposition, robust PCA, low-rank recovery from monotone missing data, and a number of other important problems. Many of these problems are NP-hard, and while algorithms with provable guarantees are known in some cases, they either run in exponential time in certain problem parameters, or make strong assumptions. In this work, we consider bicriteria algorithms, which output a rank-k' matrix L, with k' > k, that achieves error nearly as small as the optimal rank-k approximation. We show, rather surprisingly, that a common polynomial time heuristic achieves an additive epsilon*||A||_F^2 error bound with rank k' depending on the epsilon-error randomized communication complexity of the mask matrix W. For many important problems, this yields bicriteria algorithms with k' = k * poly((log n)/epsilon). We show that different models of communication yield bicriteria algorithms for natural variants of masked low-rank approximation. For example, multi-player number-in-hand communication complexity connects to tensor decomposition and non-deterministic communication complexity to Boolean low-rank factorization. We conjecture that the connection we show between masked low-rank approximation and communication complexity may be inherent and present evidence in this direction.
Authors: Cameron Musco, Christopher Musco, and David Woodruff