Mutual coherence (linear algebra) explained

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.^{[1] [2]}

Formally, let

a _{1,} \ldots, a _{m\in} { C} ^{d} be the columns of the matrix A, which are assumed to be normalized such that a ^{H} _{i} a _{i} = 1 . The mutual coherence of A is then defined as^{[1] [2]} M = max _{1} \left| a ^{H} _{i} a _{j} \right|.

A lower bound is^[3]

M\ge \sqrt{ (m - d)/(d(m -1 )) }.A deterministic matrix with the mutual coherence almost meeting the lower bound can be constructed by Weil's theorem.^[4]

This concept was reintroduced by David Donoho and Michael Elad in the context of sparse representations.^[5] A special case of this definition for the two-ortho case appeared earlier in the paper by Donoho and Huo.^[6] 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.^{[1] [2] [7]} 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 matrix as well.^[8]

See also

• Compressed sensing
• Restricted isometry property
• Babel function

Further reading

• Mutual coherence
• R1magic : R package providing mutual coherence computation.

Notes and References

1. Tropp . J.A. . March 2006 . Just relax: Convex programming methods for identifying sparse signals in noise . IEEE Transactions on Information Theory . 52 . 3 . 1030–1051 . 10.1109/TIT.2005.864420. 6496872 .
2. Donoho . D.L.. David Donoho . M. Elad . V.N. Temlyakov . January 2006 . Stable recovery of sparse overcomplete representations in the presence of noise . IEEE Transactions on Information Theory . 52 . 1 . 6 - 18 . 10.1109/TIT.2005.860430 . 14813938.
3. Welch. L. R.. Lower bounds on the maximum cross-correlation of signals. IEEE Transactions on Information Theory. 1974. 20. 3. 397–399. 10.1109/tit.1974.1055219.
4. Zhiqiang. Xu. Deterministic Sampling of Sparse Trigonometric Polynomials. Journal of Complexity. April 2011. 27. 2. 133–140. 10.1016/j.jco.2011.01.007. 1006.2221. 2613562.
5. Donoho . D.L.. David Donoho . Michael Elad . March 2003 . Optimally sparse representation in general (nonorthogonal) dictionaries via L1 minimization . Proc. Natl. Acad. Sci. . 100 . 5. 2197 - 2202 . 10.1073/pnas.0437847100. 16576749. 153464 . 2003PNAS..100.2197D. free.
6. Donoho . D.L.. David Donoho . Xiaoming Huo . November 2001 . Uncertainty principles and ideal atomic decomposition . IEEE Transactions on Information Theory . 47 . 7 . 2845 - 2862 . 10.1109/18.959265. 10.1.1.39.3696. 9500527 .
7. Fuchs . J.-J.. June 2004 . On sparse representations in arbitrary redundant bases . IEEE Transactions on Information Theory . 50 . 6 . 1341 - 1344. 10.1109/TIT.2004.828141 . 18432970.
8. Web site: Greed is good: Algorithmic results for sparse approximation . Joel A. Tropp . 2004 . 10.1.1.84.5256 .