Simple heuristics yield provable algorithms for masked low-rank approximation

Cameron Musco, Christopher Musco, David P. Woodruff

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    In the masked low-rank approximation problem, one is given data matrix A ∈ Rn×n and binary mask matrix W ∈ {0, 1}n×n. The goal is to find a rank-k matrix L for which: n n cost(L) def = X X Wi,j · (Ai,j - Li,j)2 ≤ OPT + εkAk2F , i=1 j=1 where OPT = minrank-k L cost(L) and ε is a given error parameter. Depending on the choice of W, the above problem captures factor analysis, low-rank plus diagonal decomposition, robust PCA, low-rank matrix completion, low-rank plus block matrix approximation, 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Ω(k2 /ε) or 2) make strong assumptions, for example, that A is incoherent or that the entries in W are chosen independently and uniformly at 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 k0 > k depending on the public coin partition number of W, the heuristic outputs rank-k0 L with cost(L) ≤ OPT + εkAk2F . 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 k0 = 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.

    Original languageEnglish (US)
    Title of host publication12th Innovations in Theoretical Computer Science Conference, ITCS 2021
    EditorsJames R. Lee
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959771771
    StatePublished - Feb 1 2021
    Event12th Innovations in Theoretical Computer Science Conference, ITCS 2021 - Virtual, Online
    Duration: Jan 6 2021Jan 8 2021

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    ISSN (Print)1868-8969


    Conference12th Innovations in Theoretical Computer Science Conference, ITCS 2021
    CityVirtual, Online


    • Bicriteria approximation algorithms
    • Communication complexity
    • Low-rank approximation
    • Weighted low-rank approximation

    ASJC Scopus subject areas

    • Software


    Dive into the research topics of 'Simple heuristics yield provable algorithms for masked low-rank approximation'. Together they form a unique fingerprint.

    Cite this