Musco, Cameron ;
Musco, Christopher ;
Woodruff, David P.
Simple Heuristics Yield Provable Algorithms for Masked LowRank Approximation
Abstract
In the masked lowrank 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 rankk matrix L for which:
cost(L) := ∑_{i=1}^n ∑_{j=1}^n W_{i,j} ⋅ (A_{i,j}  L_{i,j})² ≤ OPT + ε ‖A‖_F²,
where OPT = min_{rankk L̂} cost(L̂) and ε is a given error parameter. Depending on the choice of W, the above problem captures factor analysis, lowrank plus diagonal decomposition, robust PCA, lowrank matrix completion, lowrank plus block matrix approximation, lowrank recovery from monotone missing data, and a number of other important problems. Many of these problems are NPhard, and while algorithms with provable guarantees are known in some cases, they either 1) run in time n^Ω(k²/ε) 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 lowrank 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 rankk' 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 twoplayer 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 lowrank approximation. For example, multiplayer numberinhand communication complexity connects to masked tensor decomposition and nondeterministic communication complexity to masked Boolean lowrank factorization.
BibTeX  Entry
@InProceedings{musco_et_al:LIPIcs.ITCS.2021.6,
author = {Cameron Musco and Christopher Musco and David P. Woodruff},
title = {{Simple Heuristics Yield Provable Algorithms for Masked LowRank Approximation}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {6:16:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13545},
URN = {urn:nbn:de:0030drops135452},
doi = {10.4230/LIPIcs.ITCS.2021.6},
annote = {Keywords: lowrank approximation, communication complexity, weighted lowrank approximation, bicriteria approximation algorithms}
}
04.02.2021
Keywords: 

lowrank approximation, communication complexity, weighted lowrank approximation, bicriteria approximation algorithms 
Seminar: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Issue date: 

2021 
Date of publication: 

04.02.2021 
Supplementary Material: 

Full paper available at https://arxiv.org/abs/1904.09841. 