Skip to main content
edited tags
Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Source Link

Tail probability of random projection

Suppose $v\in R^n$ is a constant unit vector. $P_l$ is a random projection matrix to an $l$ dimensional subspace of $R^n$ which is uniformly sampled from $G(l,R^n)$ which is the collection of all $l$-dimensional subspace in $R^n$. What is the upper bound of the following: $$\mathbb{P}(P_lv\leq\delta)$$ What is the order of the above probability as $\delta\to0$?

Also, when $l=n$, the above probability is the indicator function $1_{\{\delta\geq1\}}$. Can we derive an upper bound of the above probability for $l<n$ such that when $l\to n$, the upper bound tends to $1_{\{\delta\geq1\}}$?