Calculating an incoherence property from sub-optimal sampling patterns

Question

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 Ψ?

Answer 1

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