# Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation

arXiv: https://arxiv.org/abs/1904.09841 · HTML: https://mlsanity.com/paper/1904.09841/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2019.

## Built on by (most cited first, 2 of 2)

- [Nonlinear Initialization Methods for Low-Rank Neural Networks](https://mlsanity.com/paper/2202.00834/) (2022)
- [Reweighted Solutions for Weighted Low Rank Approximation](https://mlsanity.com/paper/2406.02431/) (2024)

## Abstract (arXiv)

In masked low-rank approximation, one is given A ∈ ℝn × n and binary mask matrix W ∈ 0,1n × n. The goal is to find a rank-k matrix L for which: cost(L) = sumi=1n sumj = 1n Wi,j · (Ai,j - Li,j )2 ≤ OPT + ε |A|F2 , where OPT = min_rank-k hatL cost(hat L) and ε is a given error parameter. Depending on the choice of W, this problem captures factor analysis, low-rank plus diagonal decomposition, robust PCA, low-rank matrix completion, low-rank plus block matrix approximation, and many problems. Many of these problems are NP-hard, and while some algorithms with provable guarantees are known, they either 1) run in time nOmega(k2/ε) or 2) make strong assumptions, e.g., that A is incoherent or that W is 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' > k depending on the public coin partition number of W, the heuristic outputs rank-k' L with cost(L) ≤ OPT + ε |A|F2. 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 examples of masked low-rank approximation, including all those listed above, this result yields bicriteria approximation guarantees with k' = k · poly(log n/ε). Further, we show that different models of communication yield 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.