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 '15 at 15:56

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.

| improve this answer | |
  • $\begingroup$ Thansk,..Is there is any equation connecting Compressed sensing and mutual incoherence $\endgroup$ – Abhishek Sadasivan Dec 14 '15 at 20:36
  • $\begingroup$ I added an equation to the answer that uses the mutual coherence to bound the required number of measurements. $\endgroup$ – Thomas Arildsen Dec 14 '15 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 Sadasivan Dec 16 '15 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$ – Thomas Arildsen Dec 16 '15 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} $$

| improve this answer | |
  • 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 '16 at 17: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.