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.
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.
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} $$
