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