Compressive Sensing Incoherence Principle

Question

As people acquainted with Compressive Sensing would know, incoherence and sparsity are two main principles. I've been reading about compressive sampling and developed an interest into the topic. What I'm about to ask might be quite basic so sorry for that in advance.

As incoherence principle states, sensing basis and sparsifying basis must be incoherent. I can understand why it is so and I also understand why a random i.i.d. matrix would in fact give us a good incoherence. My question is, how would one determine it programmatically?

Let's say my sparse basis is the frequency domain. When one says sensing basis, is it actually the sensing matrix? Assuming that the signal is x, and sensing matrix is A, would I just calculate the coherence between fft of x and my sensing matrix? If yes, how would one do that, say, in MATLAB?

Thanks a lot.

Answer 1

Say you have measurements $y=Ax$, with a basis $\Psi$, and $A\in\mathbb R^{M\times N}$. Then we can write $y=A\Psi\hat x=\Phi\hat x$.

I then believe direct computation of the coherence requires us to solve \begin{equation} \mu = \max_{i<j} \frac{| \langle \Phi_i,\Phi_j\rangle |}{\| \Phi_i\|\| \Phi_j\|} \end{equation} where $\Phi_i$ is the $i$-th column of $\Phi$, which I think is of order $\mathcal O(N^3)$.

Now, assuming the above is correct you can compute $\Psi_i =\text{ifft}(e_i)$, where $e_i$ is a unit vector, construct $\Phi=A\Psi$, and then with a double for loop find $\mu$.

Answer 2

The mutual coherence is a kind of proxy for the Restricted Isometry Constant (RIC), because the RIC is impractical to calculate i.e. NP hard. You should note that the RIP is sufficient but not necessary for sparse reconstruction.

Here's another definition of mutual coherence - assume that you are trying to solve $$y=Ax$$ where $x$ is sparse. The mutual coherence of $A$ is given as $$u(A) = \max_{i\neq j}|A_i^HA_j| $$

The RIC is conservatively bounded by $u(A) \leq R_s(A) \leq (s-1)u(A)$, where $||x^{true}||_0=s$.

Answer 3

If you have your sensing matrix $\Phi$ and your representation matrix $\Psi$ you just need to calculate

where $\mu$ is your incoherence property and n is the number of elements in the signal.

$\Psi$ is you Fourier matrix and $\Phi$ is your sensing matrix (your A matrix). In matlab you can just calculate the maximum inner product from the n-length vectors of $\Psi$ and $\Phi$ and mutliply by $\sqrt n$ to get your incoherence value. Than check it against [1,$\sqrt n$] where low incoherence is "good".