Calculating incoherency in compressive sensing

Question

CS is based on a choice of a sensing basis $\Phi$ relative to a representation basis $\Psi$. There are many well known pair matrices for $\Phi$ and $\Psi$ like random Gaussian and FFT, and also they should have low coherency which can be calculated with:

$$\mu(\Phi, \Psi) = \sqrt n\cdot \max\limits_{1\leq k, j \leq n} \left|\langle \varphi_k, \psi_j \rangle\right|$$

Some of these Coherency values which are calculated are as: between noiselets and Haar wavelets is $\sqrt 2$. Coherence between noiselets and Daubechies $\rm D4$ and $\rm D8$ are $2.2$ and $2.9$, respectively; random matrices are largely incoherent with any fixed basis $\Psi$. My question is how can I calculate these values in matlab? can anyone provide a code example for me?

Answer 1

As a starting-point, you might try something like this:

Step 1: create random (complex-valued) matrices

rows = 32;   %number of output samples from compression matrix 
cols = 2048;  %number of input samples supplied to compression matrix
matrixA = randn(rows, cols) + 1i*randn(rows, cols); 
matrixB = randn(rows, cols)+ 1i*randn(rows, cols);

Step 2: Compute Maximum Dot-Product Magnitude

%compute all possible cross-correlations
xc = abs(matrixA * matrixB');
%find the maximum
result = max(max(abs(matrixA * matrixB')));
%todo:  scale by sqrt(n)
%...

Step 3: Beware of Amplitude Scaling Impacts

Since the coherence equation that you provided depends upon dot-products, the amplitude scaling of your matrix will effect the result. Most likely the equation you provided assumes the matrices are scaled in amplitude. For example, each column in matrixA & matrixB might need to be scaled by it's "Euclidean Norm" or "L2-Norm". You might find it helpful to read about correlation coefficients which are scaled accordingly, or revisit your equation reference just to be safe.