1
$\begingroup$

The Welch lower bound on the maximum cross-correlation (inner product) of $m$ vectors, each of $n$ elements, is given by $c_{max} = f(m, n, k)$ (eg, see Wikipedia Welch bounds). It is always assumed that $m \gt n$ (otherwise the bound is 0). Apparently the Welch bound has been widely applied in the restricted case that the vectors are real-valued and $k = 1.\;$ In that case, $c_{max} = \left[ (m-n)/(n(m-1)) \right]^{1/2},\;$ and is always real. The function has practical use in allowing us to compare the $c_{max}\;$ calculated from any given set of vectors with the theoretical minimum possible value.

In contrast, when $k > 1,\;$ then $c_{max}\;$ is frequently a complex quantity, even if the vectors are real-valued. $\;c_{max}$ becomes real only if $m >> n\;,$ or more specifically, when $m \gt \binom{n+k-1}{k}.\;$
It is unclear to me whether $c_{max}$ has any use when $k \gt 1.$

$\quad$ Q1: Does $k$ have any physical interpretation?

$\quad$ Q2: Is the Welch formula with $k \gt 1\;$ useful in any area of physics, computational science,
$\quad\quad$ electrical engineering, or telecommunications? How do you interpret complex returned values?

$\endgroup$
1
$\begingroup$

Given any collection of $m$ unit-norm (or unit-Euclidean-length) vectors in a real or complex $n$-dimensional vector space $\mathbb R^n$ or $\mathbb C^n$, let $c_{\max}$ be the maximum magnitude of the inner product between two vectors in the set. How small can $c_{\max}$ be? One answer to this question is given by the Welch bounds which are a collection of lower bounds on the minimum possible value of $c_{\max}$. These bounds apply to all collections of $m$ unit-norm vectors in $n$-dimensional space, and they even hold for the case when the collection is a multiset (and thus two vectors are identical, and so $c_{\max}$ necessarily equals $1$).

The Welch bounds are of the form $$c_{\max}^2 \geq \sqrt[k]{C_k(m,n)}, ~k = 1, 2, 3, \ldots \tag{1}$$ or more correctly $$c_{\max}^2 \geq \sqrt[k]{\max\{C_k(m,n), 0\}},~ k = 1, 2, 3, \ldots \tag{2}$$ because the function $C_k(m,n)$ can have negative value. Note for example, that for $k = 1$, $(1)$ becomes $$c_{\max}^2 \geq \frac{m-n}{n(m-1)}$$ where the right side is negative when $m < n$ and $0$ when $m = n$. This is as it should be because we know that in a $n$-dimensional space, we can always find $m \leq n$ orthonormal vectors and so $c_\max^2 = 0$ for this set. Thus, $(2)$ which becomes $$c_{\max}^2 \geq \max\left\{\frac{m-n}{n(m-1)}, 0\right\}\tag{3}$$ is a much better way of expressing the bound. When $m \gg n$ and so $(m-n)/(m-1)$ is approximately $1$, then (as Welch pointed out as also have you in your question) the right side of $(3)$ approaches $n^{-1}$ as $m \to \infty$ and so we have that $$c_\max \geq \frac{1}{\sqrt{n}}\tag{4}$$ as a limiting form of the lower bound.

Turning to the question asked about Welch bounds for $k \geq 2$, these are useful when $m \gg n$ and give larger lower bounds than the right side of $(4)$. If I remember correctly, the Welch bound for $k = 2$ gives something like $$c_\max \geq \frac{2^{1/4}}{\sqrt{n}}$$ when $m \geq \frac{n^3+n^2}{2}$ which is an improvement on $(4)$.

For a discussion of some of these points (as applied to crosscorrelations and autocorrelations instead of inner products), I refer you to my paper "Bounds on crosscorrelation and autocorrelation of sequences" in IEEE Transactions on Information Theory, November 1979 which is behind IEEE's paywall unless you have institutional access through your employer or have paid personally for IEEExplore access.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.