Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation

In masked low-rank approximation, one is given A ∈ ℝn × n and binary mask matrix W ∈ 0,1n × n. The goal is to find a rank-k matrix L for which: cost(L) = sumi=1n sumj = 1n Wi,j · (Ai,j - Li,j )2 ≤ OPT + ε |A|F2 , where OPT = min_rank-k hatL cost(hat L) and ε is a given error parameter. Depending on the choice of W, this problem captures factor analysis, low-rank plus diagonal decomposition, robust PCA, low-rank matrix completion, low-rank plus block matrix approximation, and many problems. Many of these problems are NP-hard, and while some algorithms with provable guarantees are known, they either 1) run in time nOmega(k2/ε) or 2) make strong assumptions, e.g., that A is incoherent or that W is random. In this work, we show that a common polynomial time heuristic, which simply sets A to 0 where W is 0, and then finds a standard low-rank approximation, yields bicriteria approximation guarantees for this problem. In particular, for rank k' > k depending on the public coin partition number of W, the heuristic outputs rank-k' L with cost(L) ≤ OPT + ε |A|F2. This partition number is in turn bounded by the randomized communication complexity of W, when interpreted as a two-player communication matrix. For many important examples of masked low-rank approximation, including all those listed above, this result yields bicriteria approximation guarantees with k' = k · poly(log n/ε). Further, we show that different models of communication yield algorithms for natural variants of masked low-rank approximation. For example, multi-player number-in-hand communication complexity connects to masked tensor decomposition and non-deterministic communication complexity to masked Boolean low-rank factorization.