i have an image I of size 32*32. I perform the DCT of this image using the matlab function DCT2(I). I get a sparse representation of my image which is again a 32*32 image. I construct a circulant matrix A of size 200*1024, i.e i need only 200 samples out of the total 1024. Mathematically spaeaking, what i did is take my original signal x, sparsify using dct2 call it B, then compress is using A. So i get measurements y=A.B.x . Now how do i calculate the incoherence measure from A and B. Can somebody help.

  • $\begingroup$ Your set-up is somewhat unconventional in terms of compressed sensing, because you would usually formulate your image x as sparse in the sense x = B.z (using your notation), where z is a sparse (DCT-domain) vector and B then needs to be the IDCT transform to get the image x. You would usually take the measurements of x: y = A.x = A.B.z Is there any particular reason for the somewhat "backwards" set-up you consider here? $\endgroup$ – Thomas Arildsen Dec 10 '18 at 8:33


I would like to rephrase the original problem with slightly different notation and claim that there is no need to measure the coherence of the product of the circulant matrix A and the DCT matrix B as asked by the OP.

In the compressive sensing setting, the coherence of a sensing matrix $A$ is useful when we are using it for constructing measurements $y = A \alpha$ where $\alpha$ is a sparse vector. Then, the coherence properties of $A$ can be used to give an estimate of number of measurements required in $y$ so that $\alpha$ can be recovered stably from $y$. $\alpha$ is actually a sparse representation of some signal $x$ in some orthonormal basis $\Psi$ which is represented by the equation $x = \Psi \alpha$. In this particular case, $x$ is the image 32x32, $\Psi$ is the IDCT2 transform, $\alpha$ is the sparse representation of $x$ obtained by DCT2 transformation which is the equation $\alpha = \Psi^T x$. Thus, the matrix $B$ from OP is $\Psi^T$. So the relationship between the measurements $y$ and the original signal $x$ is $y = A \Psi^T x$. The sparse recovery of $x$ from $y$ would happen in two steps.

  1. Construct $\alpha$ from $y$ by using some algorithm $\Delta$. We represent this algorithmic recovery step as: $\alpha = \Delta(A, y)$. $\Delta$ could be basis pursuit or OMP or anything else.
  2. Construct $x$ from $\alpha$ by using the equation $x = \Psi \alpha$.

In this overall recovery process, the matrix $A B = A \Psi^T$ plays no role. Hence, there is no need to measure the coherence of $AB$.

The old answer was incorrect. The coherence of a matrix $A$ doesn't change if it is pre-multiplied by an orthogonal matrix $B$ as $BA$. Coherence of a matrix can change in arbitrary ways if it is post-multiplied by an orthogonal matrix as $AB$. I am not aware of any particular results of relating the coherence of $A$ with $AB$.

Below is old answer.

You need to compute the coherence of the matrix A. B is an orthonormal matrix. So it doesn't impact coherence of the combined matrix AB . For computing the coherence of A, normalize its columns and then take pairwise inner products of the columns. The coherence is the highest inner product in magnitude of the pairs of normalized columns of A.

For more information about coherence, see my tutorial notes here .

You may also want to learn about Babel function which is a generalization of coherence.

  • $\begingroup$ It seems I cannot confirm that B being an orthonormal matrix does not affect the coherence of its product with A. I have put together a small practical demonstration here that shows this. In particular, it seems to have a severe impact on the coherence to use a circulant matrix for A. Could this be related to the fact that the DFT diagonalises a circulant matrix? See my example with a completely random matrix C in place of A which works much better together with B, coherence-wise. $\endgroup$ – Thomas Arildsen Dec 10 '18 at 9:57
  • 1
    $\begingroup$ I think I made a mistake. Inner products of columns of a matrix don't change if the matrix is left multiplied by a unitary or orthogonal matrix. But they will change if right multiplied by a unitary or orthogonal matrix. Let me see if I can find some results for this case. Meanwhile, the easiest way here would be to compute the coherence would be to compute it for the whole AB matrix. $\endgroup$ – Shailesh Kumar Dec 11 '18 at 3:43
  • 1
    $\begingroup$ @ThomasArildsen have updated my answer and agree with your observations made in the comment to the original post. $\endgroup$ – Shailesh Kumar Dec 11 '18 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.