Incoherence is sufficient for recovering a matrix
Theorem Matrix $\mathbf A$ has coherence $\mu$ and rank $r$. There exists universal constant $c, c_1, c_2 > 0$ such that, if each entry of $\mathbf A$ is observed i.i.d. with probability
$$ > p > c\frac{r \log^2 n}{n}. > $$Then $\mathbf A$ can be recovered from the unique optimal solution of the following optimization w.p. at least $1 - c_1 n^{-c_2}$:
$$ > \begin{align*} > \min_{\hat{A}} &\quad \|\|\hat{A}\|\| \quad \text{(nuclear norm)} \cr > \text{subject to} & \quad \hat A_{ij} = A_{ij}, \quad \forall (i,j) \in \Omega \text{ (observed set)} > \end{align*} > $$
Btw, coherence $\mu$ is defined as
Definition (Coherence.) Assume that matrix $\mathbf A$ is rank $r$ with SVD
$$ > \mathbf A = U\Sigma V^T > $$so $U\in \R^{n\times r}$ and $V\in \R^{n\times r}$ are orthonormal rectangular matrices (without loss $A$ can be zero-filled to be a square matrix).
Coherence of $A$ is defined as the smallest $\mu\in \R$ such that
$$ > \max_{k= 1, \ldots, n} \|U^T e_k\|^2 \le \mu\frac{r}n, \quad\max_{k= 1, \ldots, n} \|V e_k\|^2 \le \mu\frac{r}n. > $$
Note for coherence:
We first look at the property of coherence number $\mu$ from two extreme examples.
(i) For any matrix $U$ of rank $r$ with orthonormal columns, the smallest $\mu$ that satisfies $\max_{k= 1, \ldots, n} \|U^T e_k\|^2 \le \mu\frac{r}n$ is $\mu = 1$ — when $U$ consists of vectors $(\frac 1{\sqrt n},\frac 1{\sqrt n}, \ldots, \frac 1{\sqrt n})$.
(ii) On the other hand, the largest coherence of $U$ occurs when $U$ is (part of) an identity matrix — i.e. the $k$th column of $U$ be $u_k = e_k$. Then $\mu = \frac nr$ and it can be proved that this is $\mu$’s upperbound.
The coherence number $\mu$ reflects how concentrated matrix $\mathbf A$’s singular vectors ($U$, $V$ out of SVD) are. Intuitively, when coherence $\mu$ is high — the singular vectors of $\mathbf A$ are concentrated, then it’s like like having a few very important entries in the matrix that determine the rest. Random sampling would likely miss these crucial entries, making it difficult to reconstruct the matrix accurately. So we want ***in*coherence (low $\mu$).
Incoherence is not necessarily necessary though for recovering a matrix
Incoherence assumption is required exactly because of uniform sampling. But imagine this — if you have perfect control over which entry of $\mathbf A$ be observed, technically you only need $n\times r$ observations to recover a rank-$r$ matrix.
So it should be imaginable that the incoherent requirement can be relaxed when we have some control over which entry of $\mathbf A$ is observed. One way is, each entry of $\mathbf A$ is observed w.p. w.r.t. their local coherence:
Definition (Local Coherence)
For matrix $\mathbf A$ of $n_1\times n_2$ with SVD $U\Sigma V^T$ and rank $r$, its local coherences — $\mu_i$ for any row $i$ and $\nu_i$ for any column $j$ — are defined by
$$ > \begin{align*} > \text{row:}\quad & \|\|U^Te_i\|\| = \sqrt{\frac{\mu_i r}{n_1}},\quad \forall i\in [n_1]\cr > \text{column:}\quad & \|\|V^Te_i\|\| = \sqrt{\frac{\nu_i r}{n_2}},\quad \forall j\in [n_2] > \end{align*} > $$
And then
Theorem (Chen et al. 2014)
For $n_1\times n_2$ matrix $\mathbf A$ be with local coherence parameters $\lbrace \mu_i, \nu_j \rbrace$. Then exists constant $c', c_1', c_2'$ such that, if each entry $A_{ij}$ are observed independently with probability $p_{ij}$:
$$ > \begin{align*} > p_{ij} & \ge \min\lbrace c'\frac{(\mu_i + \nu_j)r\log^2(n_1 + n_2)}{\min(n_1, n_2)}, 1\rbrace\cr > p_{ij} & \ge \frac{1}{\min(n_1, n_2)^{10}} > \end{align*}. > $$Then $\mathbf A$ can be recovered from the unique optimal solution of the following optimization w.p. at least $1 - c_1'(n_1 + n_2)^{-c_2'}$ (same from the previous theorem)
$$ > \begin{align*} > \min_{\hat{A}} &\quad \|\|\hat{A}\|\| \quad \text{(nuclear norm)} \cr > \text{subject to} & \quad \hat A_{ij} = A_{ij}, \quad \forall (i,j) \in \Omega \text{ (observed set)} > \end{align*} > $$
Note that, the expected number of observations in this theorem is
$$ \sum_{i, j}p_{ij} \ge c' \frac{r \log^2 (n_1 + n_1)}{\min(n_1, n_2)}\sum_{i, j}(\mu_i + \nu_j). $$Because $U, V$ are orthogonal — $\sum_i \mu_i r/n_1 = \sum_j \nu_jr/n_2 = r$, so we further have
$$ \sum_{i, j}p_{ij}\ge 2c'\max(n_1, n_2)r\log^2(n_1 + n_2). $$Which match the previous theorem.
Reference
[1] Coherent Matrix Completion Chen et al. ICML 2014
[2] Lecture 19–20: Matrix Completion Lecture Note by V. Morgenshtern.