# Relation Between Compressed Sensing and Incoherence

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.

• There is no general equation - you'll have to investigate the performance (in the mean squared error sense) empirically. – 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.

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

• 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. – Peter K. Mar 8 '16 at 17:23