Let $U$ be a subspace of $\mathbf{R}^d$ of dimension $r$, and $P_U$ is the orthogonal projection onto $U$. The coherence of $U$ with respect to the standard basis $(e_1,e_2,...,e_d)$ is defined to be
$$\mu(U)=\frac{d}{r} \max_{1 \leq i \leq n}\|P_Ue_i\|^2$$
Given a matrix $M \in M_{n_1 \times n_2}(\mathbf{R})$ of rank $r$, we say that $M$ is $\mu_0$-incoherent if $\max(\mu(U),\mu(V)) \leq \mu_0$. Where here $U$ and $V$ are column and row space of $M$.
Also, the strong incoherence of a matrix is the max of inner product between any two columns of the matrix.
My question is is there intuition on what those number try to capture? Is there a relationship between strong incoherence and $\mu_0$-incoherence?
$\endgroup$ 11 Answer
$\begingroup$This paper suggests that the (standard) incoherence can be intuitively understood as having information not concentrated in a few rows/columns, and can also be related to some physical quantities (see the last paragraph on page 4 for some examples). In contrast, there doesn't seem to be such an intuition for strong incoherence.
The author showed that strong incoherence is actually not required for matrix completion, which is desirable since the strong incoherence was usually the dominant factor ($\mu_1 \geq \mu_0$) in previous bounds. For matrix decomposition though, both standard and strong incoherence are necessary, since they are associated to the information (statistical) and computational lower bounds respectively.
To clarify: by strong incoherence I meant the assumption A1 of Candes and recht (page 6), but I guess the strong incoherence you mentioned is more like Definition 1.1 in Arora et. al..
$\endgroup$ 1
