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.^[1][2] First explored by David Donoho and Xiaoming Huo in the late 1990s for pairs of orthogonal bases,^[3] it was later expanded by Donoho and Michael Elad in the early 2000s to study sparse representations^[4]—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.^[1][2][5]

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.^[6]

Formal definition

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

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

A lower bound is^[7]

${\displaystyle 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.^[8]

See also

• Compressed sensing
• Restricted isometry property
• Babel function