Fast exact recovery of noisy matrix from few entries: the infinity norm approach

The matrix recovery (completion) problem, a central problem in data science, involves recovering a matrix $A$ from a relatively small random set of entries. While such a task is generally impossible, it has been shown that one can recover $A$ exactly in polynomial time, with high probability, under three basic and necessary assumptions:

1. the rank of $A$ is very small compared to its dimensions (low rank),
2. $A$ has delocalized singular vectors (incoherence), and
3. the sample size is sufficiently large.

Various algorithms address this task, including convex optimization by Candes, Recht, and Tao (2009, 2010), alternating projection by Hardt and Wooters (2014), and low-rank approximation with gradient descent by Keshavan, Montanari, and Oh (2009, 2010).

In applications, Candes and Plan (2009) noted that it is more realistic to assume noisy observations. In such cases, the above approaches provide approximate recovery with small root mean square error, which is difficult to convert into exact recovery. Recently, results by Abbe et al. (2017) and Bhardwaj et al. (2023) on approximation in the infinity norm showed that one can recover $A$ even in the noisy case, provided $A$ has bounded precision.

However, beyond the three basic assumptions, they either required that the condition number of $A$ be small (2017) or that the gaps between consecutive singular values be large (2023). These additional assumptions conflict, with one requiring singular values to be close together and the other suggesting they should be far apart. It is thus natural to conjecture that neither is necessary. In this paper, we demonstrate that this is indeed the case. We propose a simple algorithm for exact recovery of noisy data, relying solely on the three basic assumptions. The core step of the algorithm is a straightforward truncated singular value decomposition, which is highly efficient.

To analyze the algorithm, we prove a new infinity norm version of the classical Davis-Kahan perturbation theorem, improving an earlier result in (2023). Our proof employs a combinatorial contour integration argument and is entirely distinct from all previous approaches.