# Compressive Sensing - Incoherence Property

Compressive Sensing is built on 2 properties: 1) the sparsity of the representation basis relative to the sampling basis and 2) the incoherence between the singular vectors from each of the 2 bases in a). On the surface this seems fine to me but he "incoherence" relationship is confusing me a little.

Some texts refer to the coherence between the bases (representation, sampling) and other refer to the coherence between each basis and the standard basis (e1, e2, e3 ...).

Is there a difference between these two statements?

"We are in the position to state our main result: if a matrix has row and column spaces that are incoherent with the standard basis, then nuclear norm minimization can recover this matrix from a random sampling of a small number of entries."

and

"Incoherent sampling ... The coherence between the sensing basis and and the representation basis". Page 3: http://authors.library.caltech.edu/10092/1/CANieeespm08.pdf

My question is related to this question: https://dsp.stackexchange.com/a/13017/4038

I cant add comment due to low reputation. I think you misunderstood @lennon310's meaning. I reviewed his answer in the link, he treated Phi as a row selection matrix. @lennon310, please consider change your word 'rectangular identity'. I know what you mean, but that is not called identity matrix. Phi (in his context) is something like

0 1 0 0 0 0
0 0 0 0 1 0
1 0 0 0 0 0
....


Only one element valued 1 in each row, as if you are selecting rows of Psi.

• well...it is a surprise you accepted my clarify, but that is @lennon310's answer. I just made it clearer to you. – ChuNan Jan 8 '14 at 0:47
• Thank you for posting. I think Phi in the context of sensing matrix (or basis) is more complicated than what you show. I accepted your clarify simply to give you more points quickly. I appreciate Lennon's replies very much. – val Jan 8 '14 at 0:58
• Thanks for your kind accepting then:) You are right. There are many kinds of sensing/sparsing basis as lennon310 also shows in his answer. I also give the credit to him by an upvoting. – ChuNan Jan 8 '14 at 1:04

Compressive sensing requires low coherent pairs. So the lower $\mu(\Phi,\Psi)$, the better. Actually is $\Phi$ is spike basis (identity matrix) with $\phi_k(t) = \delta(t-k)$, and $\Psi$ is Fourier basis with $\psi_j(t) = 1/\sqrt n e^{-i \cdot 2\pi \cdot jt/n}$, which is just the example I showed you in another question, $\mu(\Phi,\Psi) = 1$, and the maximal incoherence is achieved. It is similar that if you apply the spike basis and the orthogonal basis obtained from SVD.
Other coherence includes but not limited to: coherence between noiselets and Haar wavelets is $\sqrt2$; coherence between noiselets and Baubechies D4 and D8 are $2.2$ and $2.9$, respectively; random matrices are largely incoherent with any fi xed basis $\Psi$.