摘要：In the masked low-rank approximation problem, one is given data matrix A â^^ â"^{n Ã- n} and binary mask matrix W â^^ {0,1}^{n Ã- n}. The goal is to find a rank-k matrix L for which: cost(L) := â^'_{i=1}^n â^'_{j=1}^n W_{i,j} â k depending on the public coin partition number of W, the heuristic outputs rank-k' L with cost(L) ⤠OPT ε â-Aâ-_F². 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 cases, including all those listed above, this yields bicriteria approximation guarantees with rank k' = k â<. poly(log n/ε). Beyond this result, we show that different notions of communication complexity yield bicriteria 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.
关键词：low-rank approximation; communication complexity; weighted low-rank approximation; bicriteria approximation algorithms
