# Calculating an incoherence property from sub-optimal sampling patterns

EDIT (after comments and subject matter review)

CS is based on a choice of a sensing basis $\Phi$ relative to a representation basis $\Psi$. Using an "Incoherence Property" $\mu$ that measures the correlation between vectors from each basis it has been shown that the CS paradigm can achieve good reconstructions if the incoherence between $\Phi$ and $\Psi$ is low. Examples of low $\mu$ come from: The spike basis ($\Phi$) and the Fourier basis ($\Psi$), the noiselet basis ($\Phi$) and the wavelet basis ($\Psi$), a random matrix ($\Phi$) and a fixed basis ($\Psi$).

updated question is:

Is there a way to calculate the $\mu$ when the user is not able to chose $\Phi$ ahead of time to sample the signal, i.e. when the samples are already provided through some arbitrary sampling scheme that is sub-optimal vis-vis CS. My aim is to show/quantify, via $\mu$, that the arbitrary sampling scheme I have been given is sub-optimal if one is expecting CS to work.

ORIGINAL

With respect to Matrix Completion and Compressive Sampling (CS) I'm trying to understand how to calculate an incoherence property μ between two bases Φ and Ψ. Getting this incoherence is important because if Φ and Ψ are highly correlated there is little chance of succesfully reconstructing a signal from sparse samples. It is stated here (page 3) that μ is given by:

where n represents the number of elements in a matrix M - say an image signal.

I understand Φ to be a sensing basis and Ψ to be a sparse representation basis. I am using uniform random sampling to get a set of a samples from M. But I would also like to try arbitrary sampling patterns. (I'm not using wavelets or noiselets or Fourier coefficients - although I would like to try this eventually)

My question is:

How do I actually obtain Φ and Ψ?

$\Phi$ is the matrix that represents the way you sample your signal $x$. Actually, $\Phi$ can be an identity matrix with some rows eliminated, which means you are picking a subset of $x$.

$\Psi$ represents the basis that you choose to expand $x$: $$x = \Psi c$$ A very simple example is that $x$ is a cosine function (thus containing only one frequency component), then you can take $\Psi$ to be the Discrete Fourier (or discrete cosine) matrix and $c$ is just the coefficient of the specific frequency, and it is pretty sparse (all the coefficients on other frequencies will be zero).

Then the compressed signal $b$ can be represented as: $$b = \Phi \Psi c$$

Actually you can also view $\Phi \Psi$ as selection of the random rows of $\Psi$, then one possible option of $\Phi$ and $\Psi$ is (in Matlab):

Psi = fft(eye(n));
p = randperm(n);
Phsi = Psi(p(1:m),:); % choose the first m rows from the permutation


Psi is $\Psi$, and Phsi is $\Phi \Psi$.

For your case, yes you can use singular value decomposition on the image space. But I would prefer to

[u,s,v]=svd(M'*M); % spectrogram
Psi = s(1:m,1:m) * v(1:m,:);
U = u(1:m,:);


which indicates that you select the m most magnitude on spectrum components. Columns in v' are the orthogonal vectors that map the frequency component with the corresponding magnitude to spectrum space. Please note that you don't need u as the basis, since it is always equivalent between u * s * v' * x = b, and s * v' * x = u' * b. As a result, the compressed form is converted to: $$U'b = \Phi \Psi c$$

Hope it helps. Thanks

• @val sorry there was a typo in my Matlab code, I updated my answer for your reference. Thanks Commented Jan 7, 2014 at 18:11
• Thank you. From your post psi is my representation basis in the FFT or DCT spce. Could you clarify some things? 1) How do I get/use D(p(1:m),:) to run? 2) Why is u not needed, is it related to M'M; If I do svd(MM') instead then V is not needed, correct? Separately - I am using the CS paradigm imperfectly: Most times you choose the phi and compare this to psi to calculate whether incoherence is low. I'm already given the samples in some arbitrary pattern. Is it possible to calculate an incoherence property to show that CS is not working because the sampling basis (psi) chosen is not optimal?
– val
Commented Jan 7, 2014 at 18:12