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 matric ...

, the coherence or mutual coherence of a

matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...

''A'' is defined as the maximum absolute value of the

cross-correlation In signal processing, cross-correlation is a measure of similarity of two series as a function of the displacement of one relative to the other. This is also known as a ''sliding dot product'' or ''sliding inner-product''. It is commonly used f ...

s 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 develo ...

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, 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