3
$\begingroup$

Let $x$ be a random vector uniformly distributed on the unit sphere $\mathbb{S}^{n-1}$. Let $V$ be a linear subspace of dimension $k$ and let $P_V(x)$ be the orthogonal projection of $x$ onto $V$. I have seen quoted in the literature that \begin{align} \mathbb{P}[|\left\| P_V(x)\right\|_2 - \sqrt{k/n} | \le \epsilon] \ge 1 -2\exp(-n\epsilon^2/2). \, \, \, \, \, \, \, (1) \end{align} However, i can still not find a concrete proof. What i do understand is that for a $1$-Lipschitz function $f:\mathbb{S}^{n-1} \rightarrow \mathbb{R}$ such as $x \mapsto |\left\| P_V(x)\right\|_2$, we have that \begin{align} \mathbb{P}[|f - M_f | \le \epsilon] \ge 1 -2\exp(-n\epsilon^2/2), \, \, \, \, \, \, \, (2) \end{align} where $M_f$ is the median of $f$. (2) mostly follows from the isoperimetric inequality on the sphere. The issue though with (1) is that $\sqrt{k/n}$ does not seem to be the median of $x \mapsto |\left\| P_V(x)\right\|_2$. Is anyone able to provide a clean argument for (1) or a self-contained reference in the literature? Many thanks.

$\endgroup$

2 Answers 2

1
$\begingroup$

All k dimensional projections are the same, so you might as well look at the first K co-ordinates. The norm squared of the projection can be represented as $\frac {X_1^2 + ... + X_k^2}{ X_1^2 + ... + X_n^2} $ where the $X_i$ are i.i.d. N(0,1). I think this actually has a beta distribution. I haven't tried to get your numbers out of this but this framework seems simple.

$\endgroup$
1
$\begingroup$

One feature of concentration of measure is that once you know concentration around some of the natural "averages" (mean, median, a given quantile, a given $L^p$ norm), you can derive formally that concentration holds around all of them.

In your case $\sqrt{k/n}$ is the $L^2$-average of the function $f : x \mapsto \|P_Vx\|_2$.

This discussed in Chapter 5.2 in G.Aubrun and S.J.Szarek, Alice and Bob meet Banach:The Interface of Asymptotic Geometric Analysis and Quantum Information Theory), for the case of $L^2$ average see Exercise 5.46. This possibly won't give the constants you claim in (1).

$\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.