3.5 Coherence

While the spark , null space property (NSP), and restricted isometry property (RIP) all provide guarantees for the recovery of sparse signals, verifying that a general matrix $\Phi$ satisfies any of these properties has a combinatorial computational complexity, since in each case one must essentially consider $\left(\genfrac{}{}{0pt}{}{N}{K}\right)$ submatrices. In many settings it is preferable to use properties of $\Phi$ that are easily computable to provide more concrete recovery guarantees. The coherence of a matrix is one such property  [link] , [link] .

The coherence of a matrix $\Phi$ , $\mu \left(\Phi \right)$ , is the largest absolute inner product between any two columns ${\phi }_i$ , ${\phi }_j$ of $\Phi$ :

$$\mu \left(\Phi \right)=\underset{1\le i<j\le N}{max}\frac{\left|〈{\phi }_i,,,{\phi }_j〉\right|}{\parallel {\phi }_i{\parallel }_2{\parallel {\phi }_j\parallel }_2}.$$

It is possible to show that the coherence of a matrix is always in the range $\mu \left(\Phi \right)\in \left[\sqrt{\frac{N-M}{M(N-1)}},,,1\right]$ ; the lower bound is known as the Welch bound  [link] , [link] , [link] . Note that when $N\gg M$ , the lower bound is approximately $\mu \left(\Phi \right)\ge 1/\sqrt{M}$ .

One can sometimes relate coherence to the spark, NSP, and RIP. For example, the coherence and spark properties of a matrix can be related by employing the Gershgorin circle theorem  [link] , [link] .

(theorem 2 of [link] )

The eigenvalues of an $N\times N$ matrix $M$ with entries $m_{ij}$ , $1\le i,j\le N$ , lie in the union of $N$ discs $d_i=d_i(c_i,r_i)$ , $1\le i\le N$ , centered at $c_i=m_{ii}$ and with radius $r_i={\sum }_{j\ne i}\left|m_{ij}\right|$ .

Applying this theorem on the Gram matrix $G={\Phi }_{\Lambda }^T{\Phi }_{\Lambda }$ leads to the following straightforward result.

For any matrix $\Phi$ ,

Since $\mathrm{spark}\left(\Phi \right)$ does not depend on the scaling of the columns, we can assume without loss of generality that $\Phi$ has unit-norm columns. Let $\Lambda \subseteq \{1,...,N\}$ with $\left|\Lambda \right|=p$ determine a set of indices. We consider the restricted Gram matrix $G={\Phi }_{\Lambda }^T{\Phi }_{\Lambda }$ , which satisfies the following properties:

• $g_{ii}=1$ , $1\le i\le p$ ;
• $|g_{ij}|\le \mu \left(\Phi \right)$ , $1\le i,j\le p$ , $i\ne j$ .

From [link] , if ${\sum }_{j\ne i}|g_{ij}|<|g_{ii}|$ then the matrix $G$ is positive definite, so that the columns of ${\Phi }_{\Lambda }$ are linearly independent. Thus, the spark condition implies $(p-1)\mu \left(\Phi \right)<1$ or, equivalently, $p<1+1/\mu \left(\Phi \right)$ for all $p<\mathrm{spark}\left(\Phi \right)$ , yielding $\mathrm{spark}\left(\Phi \right)\ge 1+1/\mu \left(\Phi \right)$ .

By merging Theorem 1 from "Null space conditions" with [link] , we can pose the following condition on $\Phi$ that guarantees uniqueness.

(theorem 12 of [link] )

If

then for each measurement vector $y\in {\mathbb{R}}^M$ there exists at most one signal $x\in {\Sigma }_K$ such that $y=\Phi x$ .

[link] , together with the Welch bound, provides an upper bound on the level of sparsity $K$ that guarantees uniqueness using coherence: $K=O\left(\sqrt{M}\right)$ . Another straightforward application of the Gershgorin circle theorem ( [link] ) connects the RIP to the coherence property.

If $\Phi$ has unit-norm columns and coherence $\mu =\mu \left(\Phi \right)$ , then $\Phi$ satisfies the RIP of order $K$ with $\delta =(K-1)\mu$ for all $K<1/\mu$ .

The proof of this lemma is similar to that of [link] .

The results given here emphasize the need for small coherence $\mu \left(\Phi \right)$ for the matrices used in CS. Coherence bounds have been studied both for deterministic and randomized matrices. For example, there are known matrices $\Phi$ of size $M\times M^2$ that achieve the coherence lower bound $\mu \left(\Phi \right)=1/\sqrt{M}$ , such as the Gabor frame generated from the Alltop sequence  [link] and more general equiangular tight frames  [link] . These constructions restrict the number of measurements needed to recover a $K$ -sparse signal to be $M=O(K^{2}logN)$ . Furthermore, it can be shown that when the distribution used has zero mean and finite variance, then in the asymptotic regime (as $M$ and $N$ grow) the coherence converges to $\mu \left(\Phi \right)=\sqrt{(2logN)/M}$   [link] , [link] , [link] . Such constructions would allow $K$ to grow asymptotically as $M=O(K^{2}logN)$ , matching the known finite-dimensional bounds.

The measurement bounds dependent on coherence are handicapped by the squared dependence on the sparsity $K$ , but it is possible to overcome this bottleneck by shifting the types of guarantees from worst-case/deterministic behavior, to average-case/probabilistic behavior  [link] , [link] . In this setting, we pose a probabilistic prior on the set of $K$ -sparse signals $x\in {\Sigma }_K$ . It is then possible to show that if $\Phi$ has low coherence $\mu \left(\Phi \right)$ and spectral norm ${\parallel \Phi \parallel }_2$ , and if $K=O({\mu }^{-2}\left(\Phi \right)logN)$ , then the signal $x$ can be recovered from its CS measurements $y=\Phi x$ with high probability. Note that if we replace the Welch bound, then we obtain $K=O(MlogN)$ , which returns to the linear dependence of the measurement bound on the signal sparsity that appears in RIP-based results.