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!)

  • 1
    $\begingroup$ what is a quantifier for $i,j$? $\endgroup$ – Fedor Petrov Apr 25 at 20:40
  • $\begingroup$ Thanks. They run from $1\dots n$ and for the concentration they're not equal. I edited the question. $\endgroup$ – user27182 Apr 25 at 20:47
  • 1
    $\begingroup$ The first sentence in your post is inconsistent with the rest. What happened to the "independent" ? $\endgroup$ – dohmatob Apr 29 at 6:24
  • 1
    $\begingroup$ 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 ? $\endgroup$ – dohmatob Apr 29 at 6:28
  • $\begingroup$ @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. $\endgroup$ – user27182 Apr 29 at 6:58

I have a partial answer: Lemma 2.2 (rephrased below) from [1] gives a deterministic lower bound to the inner product by considering the gram matrix

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)}. $$

[1] Perturbed identity matrices have high rank: Proof and applications, 2009, Noga Alon

| cite | improve this answer | |
  • 1
    $\begingroup$ 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$)? $\endgroup$ – DSM Apr 29 at 11:11
  • $\begingroup$ 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}$$ $\endgroup$ – user27182 Apr 29 at 11:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Dustin G. Mixon Apr 29 at 12:52
  • $\begingroup$ @DustinG.Mixon. Thank you. I looked at the wikipedia page for welch bounds. Can you explain how I would turn them into a probabilistic statement please? (If so then you could give an answer so I could accept.) $\endgroup$ – user27182 Apr 30 at 7:29

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.