Low-Rank Approximation from Communication Complexity
share
In low-rank approximation with missing entries, given A∈R^n× n and binary W ∈{0,1}^n× n, the goal is to find a rank-k matrix L for which: cost(L)=∑_i=1^n∑_j=1^nW_i,j· (A_i,j - L_i,j)^2< OPT+ϵA_F^2, where OPT=_rank-k L̂cost(L̂). This problem is also known as matrix completion and, depending on the choice of W, captures 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 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 consider bicriteria algorithms, which output L with rank k' > k. We prove that a common heuristic, which simply sets A to 0 where W is 0, and then computes a standard low-rank approximation, achieves the above approximation bound with rank k' depending on the communicationcomplexity of W. Namely, interpreting W as the communication matrix of a Boolean function f(x,y) with x,y∈{0,1}^ n, it suffices to set k'=O(k· 2^R^1-sided_ϵ(f)), where R^1-sided_ϵ(f) is the randomized communication complexity of f with 1-sided error probability ϵ. For many problems, this yields bicriteria algorithms with k'=k· poly(( n)/ϵ). We prove a similar bound using the randomized communication complexity with 2-sided error. Further, we show that different models of communication yield algorithms for natural variants of the problem. E.g., multi-player communication complexity connects to tensor decomposition and non-deterministic communication complexity to Boolean low-rank factorization.
READ FULL TEXT