I am working on CS. I know that as coherence decreases (or incoherence increases) compressed sensing results improve. I know how to calculate the coherence, but I can't find an exact equation between incoherence and compressed sensing. I would like to know the equation relating coherence and CS with lower and higher limits.

Thanks in advance.

  • $\begingroup$ There is no general equation - you'll have to investigate the performance (in the mean squared error sense) empirically. $\endgroup$
    – Tom Kealy
    Dec 14, 2015 at 15:56

2 Answers 2


The coherence can be used to bound the number of measurements $m$ required for successful reconstruction as seen for example in equation (6) in Candès & Wakin 2008: $$m ≥ C \cdot \mu^2(\Phi, \Psi)\cdot S \cdot \log n$$ where $C$ is some positive constant, $S$ is the sparsity, and $n$ is the size of the sparse signal.

One problem, however, is that this is not a very sharp bound. Donoho & Tanner 2010, for example, describe some brief history of this in Section X of the linked paper. I have not followed the development on this aspect of compressed sensing for a long time, so I do not know if there are newer or better explanations. So, in my opinion, the best you can use the coherence for in practice is as a rule of thumb: the less coherence, the better.

  • $\begingroup$ Thansk,..Is there is any equation connecting Compressed sensing and mutual incoherence $\endgroup$
    – Abhishek
    Dec 14, 2015 at 20:36
  • $\begingroup$ I added an equation to the answer that uses the mutual coherence to bound the required number of measurements. $\endgroup$ Dec 14, 2015 at 21:38
  • $\begingroup$ Thanks,Can you tell me the limits/bounds.How far we can go or what is the minmum value of m that can be choosed $\endgroup$
    – Abhishek
    Dec 16, 2015 at 10:12
  • $\begingroup$ In my experience, the phase transition bounds from Donoho & Tanner are the most realistic and reflect practical performance well for l1 reconstruction. I would look at that instead of coherence if I were you. $\endgroup$ Dec 16, 2015 at 10:42

Coherence and incoherence with respect to compressive sensing is a feature that has to be implemented when designing your sensing matrix. See if my write up below could be of any help.

Incoherence: This is the property of the sensing matrix $A$ that aids to determine the recovery ability of $A$ (Joel, 2003) (David & Michael, 2002).

It is specifically used to determine the sufficient condition for $L_0$ and $L_1$ unique solutions (Heung-No, 2011 - Introduction to compressive sensing: With coding theory perspective). The coherence of the sensing matrix $A$ ($\mu(A)$) is the largest absolute, relative inner product between two columns $A_i$ and $A_j$ of the sensing matrix $A$ as given in (1) below (Emmanuel et al., 2010). $$ \mu(A) = \max_{j<k} \frac{|\langle A_j,A_k \rangle|}{\|A_j\|_2 \|A_k\|_2} \tag{1} $$ This property of $A$ is easier to evaluate than RIP of $A$, reason being that the computational complexity of evaluating $\mu(A)$ scales exponentially with the number of columns in $A$ (Dennis, S. 2012). The relationship between coherence and spark of $A$ is given in (2) - see reference in (Marco, 2009). If (2) holds, then for each measured vector $b \in \mathbb{R}^M$ there exist at most one signal $x$ such that $Ax=b + \epsilon$ holds. $$ k < \frac{1}{2} \left(1 + \frac{1}{\mu(A)} \right) \tag{2} $$

  • 1
    $\begingroup$ I've tried to use mathjax to enter the equations, but (1) is beyond my divining powers! If you can point me to the "Richard" reference, I'll try to fix it. $\endgroup$
    – Peter K.
    Mar 8, 2016 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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