Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » Coherence

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Coherence

Module by: Marco F. Duarte. E-mail the author

Summary: In this module we introduce coherence, which provides a more computationally friendly alternative to conditions such as the spark, NSP, or RIP. We briefly describe the theoretical relationship between these conditions.

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 ΦΦ satisfies any of these properties has a combinatorial computational complexity, since in each case one must essentially consider NKNK submatrices. In many settings it is preferable to use properties of ΦΦ that are easily computable to provide more concrete recovery guarantees. The coherence of a matrix is one such property [3], [9].

Definition 1:

The coherence of a matrix ΦΦ, μ(Φ)μ(Φ), is the largest absolute inner product between any two columns φiφi, φjφj of ΦΦ:

μ ( Φ ) = max 1 i < j N φ i , φ j φ i 2 φ j 2 . μ ( Φ ) = max 1 i < j N φ i , φ j φ i 2 φ j 2 .
(1)

It is possible to show that the coherence of a matrix is always in the range μ(Φ)N-MM(N-1),1μ(Φ)N-MM(N-1),1; the lower bound is known as the Welch bound [7], [8], [13]. Note that when NMNM, the lower bound is approximately μ(Φ)1/Mμ(Φ)1/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 [5], [12].

Theorem 1: (Theorem 2 of [5])

The eigenvalues of an N×NN×N matrix MM with entries mijmij, 1i,jN1i,jN, lie in the union of NN discs di=di(ci,ri)di=di(ci,ri), 1iN1iN, centered at ci=miici=mii and with radius ri=ji|mij|ri=ji|mij|.

Applying this theorem on the Gram matrix G=ΦΛTΦΛG=ΦΛTΦΛ leads to the following straightforward result.

Lemma 1

For any matrix ΦΦ,

spark ( Φ ) 1 + 1 μ ( Φ ) . spark ( Φ ) 1 + 1 μ ( Φ ) .
(2)

Proof

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

  • gii=1gii=1, 1ip1ip;
  • |gij|μ(Φ)|gij|μ(Φ), 1i,jp1i,jp, ijij.

From Theorem 1, if ji|gij|<|gii|ji|gij|<|gii| then the matrix GG is positive definite, so that the columns of ΦΛΦΛ are linearly independent. Thus, the spark condition implies (p-1)μ(Φ)<1(p-1)μ(Φ)<1 or, equivalently, p<1+1/μ(Φ)p<1+1/μ(Φ) for all p< spark (Φ)p< spark (Φ), yielding spark (Φ)1+1/μ(Φ) spark (Φ)1+1/μ(Φ).

By merging Theorem 1 from "Null space conditions" with Lemma 1, we can pose the following condition on ΦΦ that guarantees uniqueness.

Theorem 2: (Theorem 12 of [3])

If

K < 1 2 1 + 1 μ ( Φ ) , K < 1 2 1 + 1 μ ( Φ ) ,
(3)

then for each measurement vector yRMyRM there exists at most one signal xΣKxΣK such that y=Φxy=Φx.

Theorem 2, together with the Welch bound, provides an upper bound on the level of sparsity KK that guarantees uniqueness using coherence: K=O(M)K=O(M). Another straightforward application of the Gershgorin circle theorem (Theorem 1) connects the RIP to the coherence property.

Lemma 2

If ΦΦ has unit-norm columns and coherence μ=μ(Φ)μ=μ(Φ), then ΦΦ satisfies the RIP of order KK with δ=(K-1)μδ=(K-1)μ for all K<1/μK<1/μ.

The proof of this lemma is similar to that of Lemma 1.

The results given here emphasize the need for small coherence μ(Φ)μ(Φ) for the matrices used in CS. Coherence bounds have been studied both for deterministic and randomized matrices. For example, there are known matrices ΦΦ of size M×M2M×M2 that achieve the coherence lower bound μ(Φ)=1/Mμ(Φ)=1/M, such as the Gabor frame generated from the Alltop sequence [6] and more general equiangular tight frames [8]. These constructions restrict the number of measurements needed to recover a KK-sparse signal to be M=O(K2logN)M=O(K2logN). Furthermore, it can be shown that when the distribution used has zero mean and finite variance, then in the asymptotic regime (as MM and NN grow) the coherence converges to μ(Φ)=(2logN)/Mμ(Φ)=(2logN)/M [1], [2], [4]. Such constructions would allow KK to grow asymptotically as M=O(K2logN)M=O(K2logN), matching the known finite-dimensional bounds.

The measurement bounds dependent on coherence are handicapped by the squared dependence on the sparsity KK, but it is possible to overcome this bottleneck by shifting the types of guarantees from worst-case/deterministic behavior, to average-case/probabilistic behavior [10], [11]. In this setting, we pose a probabilistic prior on the set of KK-sparse signals xΣKxΣK. It is then possible to show that if ΦΦ has low coherence μ(Φ)μ(Φ) and spectral norm Φ2Φ2, and if K=O(μ-2(Φ)logN)K=O(μ-2(Φ)logN), then the signal xx can be recovered from its CS measurements y=Φxy=Φx with high probability. Note that if we replace the Welch bound, then we obtain K=O(MlogN)K=O(MlogN), which returns to the linear dependence of the measurement bound on the signal sparsity that appears in RIP-based results.

References

  1. Cai, T. and Jiang, T. (2010). Limiting Laws of Coherence of Random Matrices with Applications to Testing Covariance Structure and Construction of Compressed Sensing Matrices. [Preprint].
  2. Candès, E. and Plan, Y. (2009). Near-Ideal Model Selection by minimization. Ann. Stat., 37(5A), 2145–2177.
  3. Donoho, D. and Elad, M. (2003). Optimally sparse representation in general (nonorthogonal) dictionaries via minimization. Proc. Natl. Acad. Sci., 100(5), 2197–2202.
  4. Donoho, D. (2006). For most large underdetermined systems of linear equations, the minimal -norm solution is also the sparsest solution. Comm. Pure Appl. Math., 59(6), 797–829.
  5. Gervsgorin, S. (1931). Über die Abgrenzung der Eigenwerte einer Matrix. Izv. Akad. Nauk SSSR Ser. Fiz.-Mat., 6, 749–754.
  6. Herman, M. and Strohmer, T. (2009). High-Resolution Radar via Compressed Sensing. IEEE Trans. Signal Processing, 57(6), 2275–2284.
  7. Rosenfeld, M. (1996). In praise of the Gram matrix. The Mathematics of Paul Erdős II. (p. 318–323). Berlin, Germany: Springer.
  8. Strohmer, T. and Heath, R. (2003, Nov.). Grassmanian frames with applications to coding and communication. Appl. Comput. Harmon. Anal., 14(3), 257–275.
  9. Tropp, J. and Gilbert, A. (2007). Signal recovery from partial information via orthogonal matching pursuit. IEEE Trans. Inform. Theory, 53(12), 4655–4666.
  10. Tropp, J. A. (2008). Norms of random submatrices and sparse approximation. C. R. Acad. Sci. Paris, Ser. I, 346(23–24), 1271–1274.
  11. Tropp, J. A. (2008). On the conditioning of random subdictionaries. Appl. Comput. Harmon. Anal., 25, 1-24.
  12. Varga, R. (2004). Geršgorin and His Circles. Berlin, Germany: Springer.
  13. Welch, L. (1974). Lower bounds on the maximum cross correlation of signals. IEEE Trans. Inform. Theory, 20(3), 397–399.

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks