linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrices ...

, 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_1, \ldots, a_m\in ^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_ \left,  a_i^H a_j \.

A lower bound is :

M\ge \sqrt

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 David Leigh Donoho (born March 5, 1957) is an American statistician. He is a professor of statistics at Stanford University, where he is also the Anne T. and Robert M. Bass Professor in the Humanities and Sciences. His work includes the develop ...

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

signal In signal processing, a signal is a function that conveys information about a phenomenon. Any quantity that can vary over space or time can be used as a signal to share messages between observers. The '' IEEE Transactions on Signal Processing' ...

s. In particular, it is used as a measure of the ability of suboptimal algorithms such as

matching pursuit Matching pursuit (MP) is a sparse approximation algorithm which finds the "best matching" projections of multidimensional data onto the span of an over-complete (i.e., redundant) dictionary D. The basic idea is to approximately represent a signal ...

and

basis pursuit Basis pursuit is the mathematical optimization problem of the form : \min_x \, x\, _1 \quad \text \quad y = Ax, where ''x'' is a ''N''-dimensional solution vector (signal), ''y'' is a ''M''-dimensional vector of observations (measurements), ''A ...

to correctly identify the true representation of a sparse signal. Joel Tropp introduced a useful extension of Mutual Coherence, known as the

Babel function The Babel function (also known as cumulative coherence) measures the maximum total Coherence (signal processing), coherence between a fixed atom (sparse signal analysis), atom and a collection of other atoms in a dictionary (sparse signal analysis ...

, 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 matix as well.

See also

References

Further reading