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 be the columns of the matrix A, which are assumed to be normalized such that The mutual coherence of A is then defined as
A lower bound is
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.
