Skip to main content
1 of 2
Nuno
  • 269
  • 1
  • 7

Distribution of scaled Johnson-Lindenstrauss transforms

Suppose that $\mathcal{D}$ is a Johnson-Lindenstrauss (JL) distribution on $\mathbb{R}^{r\times n}$ ($1 \le r \le n$), meaning that there exist constants $\epsilon, \delta \in(0,1)$ such that $$ \mathbb{P}_{A \sim \mathcal{D}}((1 - \epsilon)\|x\| \le \|Ax\|\le (1 + \epsilon)\|x\|) \ge \delta \quad \text{for all}\quad x \in \mathbb{R}^n. $$

Question: Do there exist constants $\epsilon', \delta' \in(0,1)$ such that $$ \mathbb{P}_{A \sim \mathcal{D}}((1 - \epsilon')\|x\| \le \|S(A)\, x\|\le (1 + \epsilon')\|x\|) \ge \delta' \quad \text{for all}\quad x \in \mathbb{R}^n, $$ where $S(A) = A/\|A\|$ (scaled JL transform)? In other words, if $A$ follows a JL distribution, is the distribution of $A/\|A\|$ also a JL distribution?

Here, all the norms are the Euclidean norm or spectral norm.

Thanks.

Nuno
  • 269
  • 1
  • 7