# 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.

$$\newcommand\ep\epsilon\newcommand{\de}{\delta}\newcommand{\R}{\mathbb R}$$We have $$\begin{equation*} P((1-\ep)\|x\|\le\|Ax\|\le(1+\ep)\|x\|)\ge\de \tag{1}\label{1} \end{equation*}$$ for some $$\ep,\de$$ in $$(0,1)$$ and all $$x\in\R^n$$.
The OP asks if then $$\begin{equation*} P((1-\ep')\|x\|\le\|S(A)x\|\le(1+\ep')\|x\|)\ge\de' \tag{2}\label{2} \end{equation*}$$ for some $$\ep',\de'$$ in $$(0,1)$$ and all $$x\in\R^n$$, where $$S(A):=A/\|A\|$$.
To avoid the division by $$\|A\|$$ when $$\|A\|$$ takes the value $$0$$, rewrite \eqref{2} as $$\begin{equation*} P((1-\ep')\|A\|\|x\|\le\|Ax\|\le(1+\ep')\|A\|\|x\|)\ge\de'. \tag{2a}\label{2a} \end{equation*}$$
Let us now show that \eqref{2a} indeed holds for some $$\ep',\de'$$ in $$(0,1)$$ and all $$x\in\R^n$$. There is some real $$c>1$$ such that $$\begin{equation*} P(\|A\|>c)\le\de/2. \end{equation*}$$ Let $$\ep':=1-\dfrac{1-\ep}c$$ and $$\de':=\de/2$$, so that $$1-\ep'=\dfrac{1-\ep}c\in(0,1)$$, $$\ep'\in(0,1)$$, and $$\de'\in(0,1)$$. Then for any $$x\in\R^n$$ \begin{equation*} \begin{aligned} &P((1-\ep')\|A\|\|x\|\le\|Ax\|\le(1+\ep')\|A\|\|x\|) \\ =&P((1-\ep')\|A\|\|x\|\le\|Ax\|) \\ \ge&P(\|A\|\le c,(1-\ep')c\|x\|\le\|Ax\|) \\ =&P(\|A\|\le c,(1-\ep)\|x\|\le\|Ax\|) \\ \ge&P((1-\ep)\|x\|\le\|Ax\|)-P(\|A\|>c) \\ \ge&P((1-\ep)\|x\|\le\|Ax\|\le(1+\ep)\|x\|)-P(\|A\|>c) \\ \ge&\de-\de/2=\de', \end{aligned} \end{equation*} as claimed.
• Thank you for the answer! Is it possible to find an upper bound for the number $c$ based on $\epsilon$, $\delta$, $r$, and $n$ under some conditions? It would be great if $\epsilon'$ is in the same order as $\epsilon$, at least in some (sufficiently general) cases.
• @Nuno : At this point, I don't know about an upper bound on $c$. It would be better to ask about such a bound in a separate post. Commented Oct 30, 2022 at 3:20