Why is incoherence important for compressive sensing?

Question

The literature on compressive sensing (CS) frequently notes that CS relies on two principles: sparsity and incoherence. While I understand why the signal of interest should be sparse in some domain since CS relies on minimizing the norm, incoherence is much fuzzier to me. While equations exist that quantify the incoherence of $\Phi$ and $\Psi$, I have been trying to wrap my head around exactly why the property is important.

For reference, I am interested in applying CS to image scanning where each row of $\Phi$ is full of zeroes except for a one at a prescribed pixel (would this be called a spike basis?). It makes sense to me that $\Phi$ should be incoherent, if such means that the sampling occurs in an irregular pattern that allows maximal information to be obtained. And I see why the signal should be sparse in the $\Psi$ basis. However, I do not see how the CS result depends on the incoherence relationship between $\Phi$ and $\Psi$. Why is this so?

Answer 1

It is necessary when reconstruction is considered. Simply imagine the case when $A = \Phi \Psi$ has a high coherence, e.g. all columns are exactly the same and indistinguishable, then there is no way to tell which columns of $A$ correspond to non-zero elements of $a$ and together were contributed to vector $Y$. If you look at equation 2 below, you can say vector $Y$ is summution of columns of $\Phi \Psi$ multiplied in corresponding elements from vector $a$. When the signal is sparse (first assumption), but we do not know our measurement vector resemble which columns of $\Phi \Psi$ (hence using it to decode), our sparse reconstruction fails.

$$ Y = \Phi X ~~~~~~~~~~~~~~~~~(1)$$ $$ Y = \Phi \Psi a ~~~~~~~~~~~~~~~(2)$$

$Y$ being measurement vector and $a$ being sparse representation of signal of $X$, so $a = \Psi^{-1}X$. Basically, the problem of CS reconstruction is finding our which non-zero elements from the sparse matrix contributed to the measurement and how much was their contribution. If you do not have a unique enough corresponding column for $A$ then you cannot tell which elements were the contributor and how much was the contribution.