Coherence of a normalized matrix ($\mu (A)={\max }_{i\ne j}|⟨a_i,a_j⟩|$)

For a matrix with at least two columns of unit Euclidean norm, its mutual coherence is the largest magnitude of an inner product between distinct columns. It measures the strongest pairwise ambiguity of linear measurements. The Cauchy-Schwarz inequality gives $0\le \mu \le 1$. The order-two restricted isometry constant equals the mutual coherence, because every two-column Gram matrix has eigenvalues $1\pm |⟨a_i,a_j⟩|$.

For unit Euclidean norm columns, cumulative coherence measures the largest sum of $k$ correlations with one other column. Its domain is $0\le k\le N-1$, with ${\mu }_1(0)=0$ by the empty-sum convention. It is nondecreasing, ${\mu }_1(1)=\mu$ for $N\ge 2$, and ${\mu }_1(k)\le k\mu$, where $\mu$ is the mutual coherence. Keeping a sum of actual correlations can be substantially sharper than replacing each summand by the largest one.

For normalized columns and $1\le s\le N$, the restricted isometry constant is bounded by the cumulative coherence at $s-1$. A restricted Gram matrix has diagonal one and every off-diagonal row sum at most ${\mu }_1(s-1)$. The Gershgorin circle theorem and the finite-dimensional spectral theorem bound its eigenvalues between $1-{\mu }_1(s-1)$ and $1+{\mu }_1(s-1)$. At $s=1$ the distortion is zero, and at $s=2$ it is exactly the mutual coherence.