2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Nuno
    Commented Oct 30, 2022 at 2:41
  • $\begingroup$ @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. $\endgroup$ Commented Oct 30, 2022 at 3:20

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.