# Lower bound for mutual inner products of N random unit vectors in $\mathbb{R}^n$, N > n

I have $$N$$ independent random unit vectors $$\{v_i\}$$ in $$\mathbb{R}^n$$, where N > n. I need a concentration inequality of the form $$\text{P}(|v_i \cdot v_j| > \epsilon \,\,\,\, \forall i, j = 1, \dots, N: i \neq j)\leq \psi(\epsilon)$$ where hopefully $$\psi(\epsilon)$$ is something small.

I think that I can use Johnson-Lindenstrauss to do this for isotropic vectors (e.g. by choosing orthogonal basis for $$\mathbb{R}^N$$ and projecting into $$\mathbb{R}^n$$ with a random subgaussian matrix).

Are there results of this form that hold when the $$\{v_i\}$$ are not distributed isotropically, for instance Gaussian with covariance $$\Sigma$$? For instance, when there is some weak correlation/dependence between the components of each of the $$v$$ --- maybe $$|\Sigma_{ij}| \leq \alpha$$ when $$i\neq j$$?

(Any seemingly related results in this area are much appreciated!)

• what is a quantifier for $i,j$? Apr 25 '20 at 20:40
• Thanks. They run from $1\dots n$ and for the concentration they're not equal. I edited the question. Apr 25 '20 at 20:47
• The first sentence in your post is inconsistent with the rest. What happened to the "independent" ? Apr 29 '20 at 6:24
• Would this help $P(\cap_{i\ne j}\{|v_i^Tv_j| > \epsilon\}) \le \min_{(i,j) \mid i \ne j} P(|v_i^Tv_j| \le \epsilon)$ to begin with ? Apr 29 '20 at 6:28
• @dohmatob You are right, I will remove the word 'independent'. Thank you for your second comment. I am not sure this is what I was looking for, but I will see whether I can make something from this observation. Apr 29 '20 at 6:58

Let $$M \in \mathbb{R}^{p\times p}$$ be a rank $$d$$, real, symmetric matrix with $$M_{ii} = 1$$ $$\forall i$$ and $$|M_{ij}| \le \epsilon$$ $$i\neq j$$, then $$\epsilon^2 \ge \frac{p - d}{d(p-1)}.$$
• Interesting result to know. How do you intend to use it, given that for a full rank gram matrix (which is the precondition in the question) this would yield a trivial lower bound ($p-d = 0$)?
• Very sorry. I made a typo in the question. I have $N$ vectors in $\mathbb{R}^n$ and want to concentrate on all of them, not just $n$ of them. If $N>n$ then this lemma means I can't make the inner products arbitrarily small (which is also obvious, thinking geometrically). $$|v_i \cdot v_j| \ge \sqrt{\frac{N-n}{n(N-1)}} \ge \sqrt{1/n}$$ Apr 29 '20 at 11:46
• In OP's setting, a simple union bound argument gives that $\max_{i\neq j}|v_i\cdot v_j|=O(\sqrt{(\log N)/n})$ with probability $1-O(1/N)$, so this bound (known as the Welch bound) is optimal up to logarithmic factors. Apr 29 '20 at 12:52