0
$\begingroup$

Let $A_1,\dots,A_n\in \mathbb{R}^{d\times d}$ be some matrices. Suppose we sample $x_1,\dots,x_n,y\sim \mathcal{U}(\mathbb{S}^{d-1})$, where $\mathcal{U}(\mathbb{S}^{d-1})$ is the uniform distribution over the unit sphere. I want to show that with high probability over the samples we have:

$ \left\langle \frac{A_1x_1 + \dots A_nx_n}{||A_1x_1 + \dots A_nx_n||}, y \right\rangle \leq c \cdot \frac{1}{\sqrt{d}} $

where $c$ is some constant.

Now, for one vector and one matrix, I can show it using standard concentration arguments with $c=2$ and get that the correlation is small with probability exponentially close to $1$.

I don't know how to generalize it to a general number of matrices. My intuition is that it is still true since it looks impossible to pick matrices $A_i$ which after the normalization will have a high correlation for all choices of the $x_i$'s and $y$.

As a side note, I'm also interested in the case that all the distributions are Gaussian $\mathcal{N}\left(0,\frac{1}{d}I\right)$ instead of uniform over the unit sphere - but we still normalize over the sum.

$\endgroup$

1 Answer 1

2
$\begingroup$

Is $Y$ independent of $(X_1,\ldots,X_n)$? If yes, write it.

If yes, it suffices to prove that for any fixed unit vector $u$, $\langle u,Y \rangle \le c/\sqrt{d}$ with high probability. By rotational invariance, one may assume that $u$ is $e_d$, the last vector of the canonical basis of $\mathbb {R}^d$.

Moreover, the random variable $Y$ can be constructed as $Z/|Z|$, where $Z \leadsto \mathcal{N}(0,O_d)$. Then $$\langle u,Y \rangle \le c/\sqrt{d} \iff Z_d \le (c/\sqrt{d})|Z| \iff Z_d^2 \le (c^2/d)(Z_1^2 + \cdots + Z_d^2).$$

Since $Z_1^2 + \cdots Z_{d-1}^2$ and $Z_d^2$ are independent r.v. with distributions Gamma$((d-1)/2,1/2)$ and Gamma$(1/2,1/2)$, the distribution of$Z_d^2/(Z_1^2 + \cdots Z_{d-1}^2)$ is Beta $(1/2,(d-1)/2)$, so the probability above can be computed explicitely.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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