5
$\begingroup$

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."

Page 6: http://statweb.stanford.edu/~candes/papers/MatrixCompletion.pdf

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ well...it is a surprise you accepted my clarify, but that is @lennon310's answer. I just made it clearer to you. $\endgroup$
    – ChuNan
    Commented Jan 8, 2014 at 0:47
  • $\begingroup$ 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. $\endgroup$
    – val
    Commented Jan 8, 2014 at 0:58
  • $\begingroup$ 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. $\endgroup$
    – ChuNan
    Commented Jan 8, 2014 at 1:04
6
$\begingroup$

I am trying to answer your question about incoherence here rather than update my previous answer on another question of yours.

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$.

You may refer to Candes-Romberg theorem for more details on incoherent sampling.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thank you again for following this up. I believe I understand what you are telling me. However my sampling does not come from the application of any of these bases that you mention. For example: given a matrix M that indicates the sample locations with 1's i.e. M = [1 0 0 1; 0 0 1 0; 0 1 0 1; 1 0 1 0], how do I decide if this is random enough to be incoherent with a fixed basis (I cannot change the sampling)? or does that not make sense to ask? $\endgroup$
    – val
    Commented Jan 7, 2014 at 19:54
  • $\begingroup$ Is M is your image, it is already sparse enough. If it is Phi, it is equivalent to an identity matrix (you can do some Gaussian elimination to prove that), so should be incoherent with the Psi basis. $\endgroup$
    – lennon310
    Commented Jan 7, 2014 at 20:19
  • $\begingroup$ M is not Phi. The M I gave is only a "toy example" showing the locations of data samples using 1s (1s are not the actual values). The real case is a matrix that is 130 x 3500, not sparse but compressible based on small singular values. $\endgroup$
    – val
    Commented Jan 7, 2014 at 20:33
  • $\begingroup$ you can choose the vectors corresponding to the 1st m biggest singular values to form the Psi, this is equivalent of a rectangular identity (m*n, where m<130) Phi multiplication and it is incoherent with any of the basis you got from SVD $\endgroup$
    – lennon310
    Commented Jan 7, 2014 at 21:04
  • $\begingroup$ In summary: 1) [u s v] = svd(M'M); 2) Psi = v'(1:m,:) = Psi; 3) Phi = ? $\endgroup$
    – val
    Commented Jan 7, 2014 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.