Distribution of scaled Johnson-Lindenstrauss transforms

Question

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.

Answer 1

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