Mutual coherence (linear algebra)

In linear algebra, the coherence or mutual coherence of a matrix A is defined as the maximum absolute value of the cross-correlations between the columns of A. Formally, let [math]\displaystyle{ a_1, \ldots, a_m\in {\mathbb C}^d }[/math] be the columns of the matrix A, which are assumed to be normalized such that [math]\displaystyle{ a_i^H a_i = 1. }[/math] The mutual coherence of A is then defined as

[math]\displaystyle{ M = \max_{1 \le i \ne j \le m} \left| a_i^H a_j \right|. }[/math]

A lower bound is

[math]\displaystyle{ M\ge \sqrt{\frac{m-d}{d(m-1)}} }[/math]

A deterministic matrix with the mutual coherence almost meeting the lower bound can be constructed by Weil's theorem.

This concept was reintroduced by David Donoho and Michael Elad in the context of sparse representations. A special case of this definition for the two-ortho case appeared earlier in the paper by Donoho and Huo. The mutual coherence has since been used extensively in the field of sparse representations of signals. In particular, it is used as a measure of the ability of suboptimal algorithms such as matching pursuit and basis pursuit to correctly identify the true representation of a sparse signal. Joel Tropp introduced a useful extension of Mutual Coherence, known as the Babel function, which extends the idea of cross-correlation between pairs of columns to the cross-correlation from one column to a set of other columns. The Babel function for two columns is exactly the Mutual coherence, but it also extends the coherence relationship concept in a way that is useful and relevant for any number of columns in the sparse representation matrix as well.

See also

• Compressed sensing
• Restricted isometry property
• Babel function

Further reading

• Mutual coherence
• R1magic : R package providing mutual coherence computation.