Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation

Abstract

In masked\ low-rank\ approximation, one is given A R^n n and binary mask matrix W \0,1\^n n. The goal is to find a rank-k matrix L for which: where OPT = _rank-k\ L cost( 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 n^(k^2/) 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\|_F^2. 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( 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.

Tasks

Reproductions