The Welch bound

Everything below is written for real vectors. The complex case changes only the transpose to a conjugate transpose, and one dimension count in Section 8, and I flag both places.

1. Setup and the question

Take $N$ unit vectors $x_1,\dots,x_N\in\mathbb{R}^d$. Their pairwise overlaps are the inner products $\langle x_i,x_j\rangle$, and since the vectors have unit length these are cosines of the angles between them. The quantity we care about is the worst overlap,

which is called the coherence of the set. Small coherence means every pair is close to orthogonal.

If $N\le d$ you can make $\mu=0$ by picking orthonormal vectors. Once $N \gt d$ that is impossible, because $d$-dimensional space has only $d$ mutually orthogonal directions. The question is quantitative. With $N \gt d$ vectors, how small can $\mu$ be? The Welch bound answers with a floor that depends only on $N$ and $d$.

Plug in two cases to get a feel. With $N=d+1$ the floor is $\mu^2\ge 1/d^2$, so $\mu\ge 1/d$. With $N\to\infty$ the floor tends to $1/d$, so no matter how many vectors you add, you cannot push coherence below roughly $1/\sqrt d$. The whole proof is one identity about a matrix plus one application of the inequality $\|A\|_F^2\ge 0$.

2. The Gram matrix, computed two ways

Stack the vectors as columns of a matrix $X\in\mathbb{R}^{d\times N}$. Two products of $X$ with itself appear throughout.

Four facts about these, each one line.

• $G$ has ones on the diagonal, because $\|x_i\|=1$. Its off-diagonal entries are exactly the overlaps we want to control.
• $\operatorname{rank}(G)\le d$, since $G=X^\top X$ and $X$ has only $d$ rows. This is the only place the dimension $d$ enters.
• $\operatorname{tr}(S)=\sum_i \|x_i\|^2 = N$.
• The squared Frobenius norms agree, $\|G\|_F^2=\|S\|_F^2$. Both equal $\operatorname{tr}(X^\top X X^\top X)$, using $\|A\|_F^2=\operatorname{tr}(A^\top A)$ and the cyclic property $\operatorname{tr}(ABC)=\operatorname{tr}(CAB)$.

The last fact is the hinge of the proof. The same number $\|G\|_F^2$ can be read off $G$, where it is a sum of squared overlaps, or off $S$, where it is constrained by the small dimension $d$. Comparing the two readings gives the bound.

3. The frame potential inequality

Reading $\|G\|_F^2$ off $G$ gives a sum over all $N^2$ pairs,

Benedetto and Fickus call this the frame potential of the set. Reading it off $S$ gives the following.

Same proof in eigenvalue language, which some people find more transparent. $S$ is symmetric positive semidefinite with eigenvalues $\lambda_1,\dots,\lambda_d\ge 0$ summing to $\operatorname{tr}(S)=N$. Cauchy–Schwarz on the vector $(\lambda_1,\dots,\lambda_d)$ against the all-ones vector gives $(\sum_k\lambda_k)^2\le d\sum_k\lambda_k^2$, that is $N^2\le d\,\|S\|_F^2$, with equality when all $\lambda_k$ are equal to $N/d$. The vectors $x_i$ must then spread their total "energy" $N$ evenly across all $d$ directions.

Theorem 1 says tight frames are precisely the minimizers of the frame potential. That is the content of Benedetto and Fickus (2003); the proof above follows their Section 2 in compressed form.

4. From the frame potential to the Welch bound

Split the frame potential into its $N$ diagonal terms, each equal to $1$, and its $N(N-1)$ off-diagonal terms.

Each off-diagonal term is at most $\mu^2$, so the sum is at most $N(N-1)\mu^2$. Combine with Theorem 1.

That is the Welch bound. The derivation used two inequalities, and each has its own equality condition.

There is a useful intermediate statement. Skipping the max step and keeping the average gives the mean-square version,

with equality for every tight frame, equiangular or not. Since a maximum is at least the mean, $\mu^2\ge\overline{\mu^2}$, and the Welch bound follows again. The mean-square version is the one that matters for associative memories like the delta rule, and Section 10 returns to it.

5. Three worked examples

$d=2$, $N=3$. Three vectors at 120°

Welch gives $\mu^2\ge\frac{3-2}{2\cdot 2}=\frac14$, so $\mu\ge\frac12$. Take $x_1=(1,0)$, $x_2=(-\tfrac12,\tfrac{\sqrt3}{2})$, $x_3=(-\tfrac12,-\tfrac{\sqrt3}{2})$. Every pair has inner product $\cos 120^\circ=-\tfrac12$, so $\mu=\tfrac12$ and the bound is met. Check tightness directly,

This set is sometimes called the Mercedes-Benz frame.

$d=3$, $N=6$. The six diagonals of an icosahedron

Welch gives $\mu^2\ge\frac{6-3}{3\cdot 5}=\frac15$, so $\mu\ge 1/\sqrt5\approx 0.447$. The icosahedron has twelve vertices in six antipodal pairs. The six lines through opposite vertices pairwise make the same angle, with $|\cos|=1/\sqrt5$. Choosing one unit vector per line gives an ETF. With $\varphi=(1+\sqrt5)/2$, the vectors $(0,\pm 1,\varphi)$, $(\pm 1,\varphi,0)$, $(\varphi,0,\pm 1)$, each divided by $\sqrt{1+\varphi^2}$, do it. The sandbox below has this as a preset so you can see an optimizer find $0.447$ from a random start.

$d=2$, $N=4$. The bound is not met

Welch gives $\mu^2\ge\frac{4-2}{2\cdot 3}=\frac13$, so $\mu\ge 0.577$. The best you can do is four lines in the plane spaced $45^\circ$ apart, which gives $\mu=\cos 45^\circ\approx 0.707$. The gap exists because equality would need four equiangular lines in the plane, and the plane holds at most three. Section 8 proves the general version of that count.

6. Sandbox

Pick $N$ and $d$, sample random unit vectors, then let gradient descent try to push the coherence down. The heatmap shows $|G_{ij}|$. The chart shows the Welch floor as a function of $N$ for the current $d$, the asymptote $1/\sqrt d$, and the Gerzon limit beyond which no ETF exists (Section 8).

7. Higher-order Welch bounds

Welch's paper proves a family of bounds, one for each integer $k\ge 1$,

and $k=1$ is the bound above. The derivation reuses Theorem 1 on a cleverly chosen set of vectors, so nothing new is needed beyond one construction.

Which $k$ gives the strongest bound depends on $N$ and $d$. For $N$ a little above $d$ the $k=1$ bound wins. For $N$ large relative to $d$ the higher-order ones take over, and as $N\to\infty$ they force $\mu\to 1$, which is correct since you cannot keep adding lines in a fixed dimension without some pair getting arbitrarily close. In the complex case the same argument works with the Hermitian inner product, $|\langle x^{\otimes k},y^{\otimes k}\rangle|=|\langle x,y\rangle|^k$, and the same $D$.

8. When the bound is not tight

Equality in the $k=1$ bound needs an ETF, and ETFs cannot have too many vectors. The following count is due to Gerzon and the proof is a Gram-matrix argument one level up, on matrices instead of vectors.

So for $N \gt d(d+1)/2$ real vectors, or $N \gt d^2$ complex ones, the Welch $k=1$ bound is strictly loose. In that range a different bound applies.

This is stated without proof. It is met in some dimensions. In $\mathbb{C}^d$ with $d$ a prime power, $d+1$ mutually unbiased bases (orthonormal bases whose cross inner products all have magnitude $1/\sqrt d$) give $N=d(d+1)$ vectors with $\mu=1/\sqrt d$ exactly. The $d=2$, $N=4$ example from Section 5 is the smallest instance, and $1/\sqrt2\approx 0.707$ is exactly the orthoplex value there.

Even inside the Gerzon range an ETF need not exist for a given $(d,N)$. In $\mathbb{R}^3$ ETFs exist for $N=3,4,6$ but not $N=5$. Deciding existence is a hard combinatorial problem connected to strongly regular graphs and difference sets, and Fickus and Mixon maintain tables of what is known. The practical reading is that the Welch bound is a clean lower bound, tight in a specific list of cases, and the true optimum (the Grassmannian packing problem, after the space of lines through the origin) is only known numerically for most $(d,N)$.

9. Random vectors against the bound

How close do random unit vectors get? Draw $x,y$ independently and uniformly on the unit sphere in $\mathbb{R}^d$. By symmetry $\mathbb{E}\langle x,y\rangle^2 = \mathbb{E}\,x_1^2 = 1/d$ (the expectation of one squared coordinate, since all $d$ coordinates share $\sum_i x_i^2=1$). So the mean-square overlap of $N$ random vectors is about $1/d$, while the Welch floor on the mean square is $\frac{N-d}{d(N-1)} \lt \frac1d$. In the mean-square sense random vectors are nearly optimal, and the gap closes as $N$ grows.

The maximum is a different story. A single overlap $\langle x,y\rangle$ is approximately Gaussian with variance $1/d$ when $d$ is large, and the coherence is the maximum of $\binom N2$ such quantities. The maximum of $M$ roughly independent Gaussians with variance $\sigma^2$ sits near $\sigma\sqrt{2\ln M}$, so

compared with the Welch floor of about $1/\sqrt d$. Random packings lose a factor of order $\sqrt{\log N}$ in the worst pair. If your application is governed by the typical pair, randomness is fine. If it is governed by the worst pair, structured constructions earn their place. Run the sandbox with $30$ vectors in $\mathbb{R}^4$ to see both numbers at once, with the RMS near the floor and the max well above it.

One more constraint that Welch does not impose. The frame potential controls squared overlaps, not their signs, so a set can have many negative overlaps. The signed total is still pinned down, since $\sum_{i\ne j}\langle x_i,x_j\rangle = \|\sum_i x_i\|^2 - N \ge -N$. The average signed overlap is therefore at least $-1/(N-1)$, with equality when the vectors sum to zero, as the simplex does.

10. Where it shows up in ML

Superposition in a delta-rule memory

Linear attention variants like DeltaNet store key-value pairs in a matrix memory $S$ and update it with the delta rule (Schlag, Irie and Schmidhuber, 2021). Say there are $V$ keys, each a unit vector $k_a\in\mathbb{R}^{d_k}$. Writing $(k_a,v_b)$ with step size $\beta$ and residual $\delta=v_b-Sk_a$ changes the read for another key $k_c$ by $\beta\,\delta\,(k_a^\top k_c)$. The interference coefficient is a Gram entry. When $V \gt d_k$ the mean-square version of the bound from Section 4 reads

and the proof is the one in Section 3 with $G=K^\top K$. Three consequences. Training can move interference between pairs and flip its sign, but the total squared interference has a floor of $V^2/d_k - V$ that no key geometry escapes. The floor is on the mean square, so a learned key set can still make a few pairs nearly orthogonal at the cost of others, so the interesting question becomes how training chooses to spread interference it can't avoid. And since the sign is free up to the constraint at the end of Section 9, negative overlaps that suppress competing keys are available to the optimizer without violating anything.

Superposition in toy models

Elhage et al. (2022) study networks that represent more features than they have neurons by assigning features to nearly orthogonal directions. The Welch bound is the exact statement of what "nearly" can mean for $N$ features in $d$ dimensions, and the Gerzon bound caps how many features can share one common interference level.

Sparse recovery

For a dictionary $D\in\mathbb{R}^{d\times N}$ with unit columns and coherence $\mu$, Donoho and Elad (2003) show that any signal with a representation using fewer than $\frac12(1+1/\mu)$ atoms has that representation uniquely. Welch bounds $\mu$ below by about $1/\sqrt d$, so coherence-based guarantees can never certify sparsity beyond about $\sqrt d/2$. Stronger guarantees need the restricted isometry property, which is where the field went next.

The original setting

Welch wrote the paper for spread-spectrum communication, where $N$ users each get a signature sequence of length $d$ and cross-correlation between signatures is interference between users. The bound says how many users a code length can support at a given interference level.

11. Exercises

Numerical check

import numpy as np

def welch(N, d):
    return np.sqrt(max(0.0, (N - d) / (d * (N - 1))))

# Mercedes-Benz frame, d=2, N=3
X = np.array([[1, 0],
              [-0.5,  np.sqrt(3)/2],
              [-0.5, -np.sqrt(3)/2]]).T        # shape (d, N)
G = X.T @ X
mu = np.abs(G - np.eye(3)).max()
print(mu, welch(3, 2))                          # 0.5 0.5
print(np.allclose(X @ X.T, 1.5 * np.eye(2)))    # True, tight

# random vectors: RMS near 1/sqrt(d), max well above the floor
rng = np.random.default_rng(0)
d, N = 64, 4000
R = rng.standard_normal((d, N)); R /= np.linalg.norm(R, axis=0)
G = R.T @ R; off = G[~np.eye(N, dtype=bool)]
print(np.sqrt((off**2).mean()), np.abs(off).max(), welch(N, d), 1/np.sqrt(d))

12. Reading

1. L. R. Welch, "Lower bounds on the maximum cross correlation of signals," IEEE Transactions on Information Theory 20(3), 1974. The original. Short, and the higher-order bounds are all there.
2. J. J. Benedetto and M. Fickus, "Finite normalized tight frames," Advances in Computational Mathematics 18, 2003. Frame potential, Theorem 1 above, and the fact that its local minimizers are tight frames.
3. T. Strohmer and R. W. Heath Jr., "Grassmannian frames with applications to coding and communication," Applied and Computational Harmonic Analysis 14, 2003. The clearest short treatment of Welch, Gerzon and orthoplex together, with the communications motivation. Sections 2 and 3, about 40 minutes.
4. S. Waldron, An Introduction to Finite Tight Frames, Birkhäuser, 2018. Textbook. Chapter 2 for tight frames and the frame potential, Chapter 12 for equiangular lines.
5. J. H. Conway, R. H. Hardin and N. J. A. Sloane, "Packing lines, planes, etc.: packings in Grassmannian spaces," Experimental Mathematics 5, 1996. The orthoplex bound in the form stated here, plus numerical packings.
6. M. Fickus and D. G. Mixon, "Tables of the existence of equiangular tight frames," arXiv:1504.00253, 2015. Which $(d,N)$ admit an ETF.
7. N. Elhage et al., "Toy Models of Superposition," Anthropic / Transformer Circuits, 2022. The ML superposition picture.
8. I. Schlag, K. Irie and J. Schmidhuber, "Linear Transformers Are Secretly Fast Weight Programmers," ICML 2021. The delta-rule memory used in Section 10.
9. D. L. Donoho and M. Elad, "Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell^1$ minimization," PNAS 100(5), 2003. Coherence-based uniqueness of sparse representations.