Mutual coherence (linear algebra)

In linear algebra, mutual coherence (or simply coherence) measures the maximum similarity between any two columns of a matrix, defined as the largest absolute value of their cross-correlations. First explored by David Donoho and Xiaoming Huo in the late 1990s for pairs of orthogonal bases, it was later expanded by Donoho and Michael Elad in the early 2000s to study sparse representations—where signals are built from a few key components in a larger set.

In signal processing, mutual coherence is widely used to assess how well algorithms like matching pursuit and basis pursuit can recover a signal’s sparse representation from a collection with extra building blocks, known as an overcomplete dictionary.

Joel Tropp extended this idea with the Babel function, which applies coherence from one column to a group, equaling mutual coherence for two columns while broadening its use for larger sets with any number of columns.

Formal definition

Formally, let $a_{1},\ldots ,a_{m}\in {\mathbb {C} }^{d}$ be the columns of the matrix A, which are assumed to be normalized such that $a_{i}^{H}a_{i}=1.$ The mutual coherence of A is then defined as

$M=\max _{1\leq i\neq j\leq m}\left|a_{i}^{H}a_{j}\right|.$

A lower bound is

$M\geq {\sqrt {\frac {m-d}{d(m-1)}}}.$

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

See also

• Compressed sensing
• Restricted isometry property
• Babel function

Further reading

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