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
A lower bound is
A deterministic matrix with the mutual coherence almost meeting the lower bound can be constructed by Weil's theorem.
The concept was introduced in a slightly less general framework by David Donoho and Xiaoming Huo, and 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.