Compressive Sensing Incoherence Principle 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.
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&lt;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$.