Mutual coherence (linear algebra)

In linear algebra, mutual coherence (or simply coherence) measures the maximum similarity between any two columns of a matrix, defined as the largest absolute value of their cross-correlations.{{cite journal |last=Tropp |first=J.A. |date=March 2006 |title=Just relax: Convex programming methods for identifying sparse signals in noise |url=https://authors.library.caltech.edu/9040/1/TROieeetit06.pdf |journal=IEEE Transactions on Information Theory |volume=52 |issue=3 |pages=1030–1051 |doi=10.1109/TIT.2005.864420 |s2cid=6496872}}{{cite journal |last=Donoho |first=D.L. |author-link=David Donoho |author2=M. Elad |author3=V.N. Temlyakov |date=January 2006 |title=Stable recovery of sparse overcomplete representations in the presence of noise |journal=IEEE Transactions on Information Theory |volume=52 |issue=1 |pages=6–18 |doi=10.1109/TIT.2005.860430 |s2cid=14813938}} First explored by David Donoho and Xiaoming Huo in the late 1990s for pairs of orthogonal bases,{{cite journal |last=Donoho |first=D.L. |author-link=David Donoho |author2=Xiaoming Huo |date=November 2001 |title=Uncertainty principles and ideal atomic decomposition |journal=IEEE Transactions on Information Theory |volume=47 |issue=7 |pages=2845–2862 |citeseerx=10.1.1.39.3696 |doi=10.1109/18.959265 |s2cid=9500527}} it was later expanded by Donoho and Michael Elad in the early 2000s to study sparse representations{{cite journal |last=Donoho |first=D.L. |author-link=David Donoho |author2=Michael Elad |date=March 2003 |title=Optimally sparse representation in general (nonorthogonal) dictionaries via L1 minimization |journal=Proc. Natl. Acad. Sci. |volume=100 |issue=5 |pages=2197–2202 |bibcode=2003PNAS..100.2197D |doi=10.1073/pnas.0437847100 |pmc=153464 |pmid=16576749 |doi-access=free}}—where signals are built from a few key components in a larger set.

In signal processing, mutual coherence is widely used to assess how well algorithms like matching pursuit and basis pursuit can recover a signal’s sparse representation from a collection with extra building blocks, known as an overcomplete dictionary.{{cite journal |last=Fuchs |first=J.-J. |date=June 2004 |title=On sparse representations in arbitrary redundant bases |journal=IEEE Transactions on Information Theory |volume=50 |issue=6 |pages=1341–1344 |doi=10.1109/TIT.2004.828141 |s2cid=18432970}}

Joel Tropp extended this idea with the Babel function, which applies coherence from one column to a group, equaling mutual coherence for two columns while broadening its use for larger sets with any number of columns.{{cite web |author=Joel A. Tropp |date=2004 |title=Greed is good: Algorithmic results for sparse approximation |url=http://web.math.princeton.edu/tfbb/spring03/greed-ticam0304.pdf |citeseerx=10.1.1.84.5256}}

Formal definition

Formally, let $a_1, \ldots, a_m\in {\mathbb C}^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_{1 \le i \ne j \le m} \left| a_i^H a_j \right|.$

A lower bound is{{cite journal|last=Welch|first=L. R.|title=Lower bounds on the maximum cross-correlation of signals|journal=IEEE Transactions on Information Theory|year=1974|volume=20|issue=3|pages=397–399|doi=10.1109/tit.1974.1055219}}

: $M\ge \sqrt{\frac{m-d}{d(m-1)}}.$

A deterministic matrix with the mutual coherence almost meeting the lower bound can be constructed by Weil's theorem.{{cite journal|last=Zhiqiang|first=Xu|title=Deterministic Sampling of Sparse Trigonometric Polynomials|journal=Journal of Complexity|date=April 2011|volume=27|issue=2|pages=133–140|doi=10.1016/j.jco.2011.01.007|arxiv=1006.2221|s2cid=2613562}}

Mutual coherence (linear algebra)

Formal definition

See also

References

Further reading