Cumulative coherence (${\mu }_1(k)={\max }_i{\max }_{|S|=k,i\notin S}{\sum }_{j\in S}|⟨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.