## Abstract

In the masked low-rank approximation problem, one is given data matrix 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: n n cost(L) ^{def} = X X Wi,j · (Ai,j - Li,j)^{2} ≤ OPT + εkAk^{2}_{F} , i=1 j=1 where OPT = min_{rank-}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 k^{0} > k depending on the public coin partition number of W, the heuristic outputs rank-k^{0} L with cost(L) ≤ OPT + εkAk^{2}_{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^{0} = 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 language | English (US) |
---|---|

Title of host publication | 12th Innovations in Theoretical Computer Science Conference, ITCS 2021 |

Editors | James R. Lee |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771771 |

DOIs | |

State | Published - Feb 1 2021 |

Event | 12th Innovations in Theoretical Computer Science Conference, ITCS 2021 - Virtual, Online Duration: Jan 6 2021 → Jan 8 2021 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 185 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 12th Innovations in Theoretical Computer Science Conference, ITCS 2021 |
---|---|

City | Virtual, Online |

Period | 1/6/21 → 1/8/21 |

## Keywords

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

## ASJC Scopus subject areas

- Software