Johnson-Lindenstrauss lemma

[[concept]]

Topics

const fieldName = "theme"; // Your field with links
const oldPrefix = "Thoughts/01 Themes/";
const newPrefix = "Digital Garden/Topics/";
 
const relatedLinks = dv.current()[fieldName];
 
if (Array.isArray(relatedLinks)) {
    // Map over the links, replace the path, and output only clickable links
    dv.el("span",
        relatedLinks
            .map(link => {
                if (link && link.path) {
                    let newPath = link.path.startsWith(oldPrefix)
                        ? link.path.replace(oldPrefix, newPrefix)
                        : link.path;
                    return dv.fileLink(newPath);
                }
            })
            .filter(Boolean).join(", ") 
	// Remove any undefined/null items
    );
} else {
    dv.el(dv.current().theme);
}
 
 

Theorem

Theorem (Johnson-Lindenstrauss)

Let $y_1,\dots ,y_n\in {\mathbb{R}}^m$ and fix $\epsilon \in (0,1)$. Let $\hat{G}\sim \mathcal{N}{\left(0,\frac{1}{d}\right)}^{\otimes d\times m}$. Suppose that $d\ge 24\frac{\log n}{{\epsilon }^2}$ And denote $(\ast )$ as the event that multiplication by $\hat{G}$ is pairwise $\epsilon$- faithful for the $y_i$. Then we have
$\mathbb{P}[(\ast )]\ge 1-\frac{1}{n}$

Proof

Note that being $\epsilon$-faithful pairwise to the $y_i$ requires the preservation of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ vector norms within a factor of $1\pm \epsilon$.

note we can do this for any $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ vectors and in particular the $y_i$ specified in the statement!

Let $x\in {\mathbb{R}}^m$. Recall that the distribution of $\hat{G}x$ is $\mathcal{N}\left(0,\frac{1}{d}||x|{|}^2{I}_d\right)$. Thus we have

\mathbb{P}_{\hat{G} \sim {\cal N\left( 0, \frac{1}{d} \right)}^{\otimes d\times m}} \left[\,\left\lvert \,\lvert \lvert \hat{G}x \rvert \rvert^2 - \lvert \lvert x \rvert \rvert ^2 \, \right\rvert >\varepsilon \lvert \lvert x \rvert \rvert ^2\,\right] &= \mathbb{P}_{g \sim {\cal N}\left( 0, \frac{1}{d} \lvert \lvert x \rvert \rvert ^2 \right)} \left[ \,\left\lvert \,\lvert \lvert g \rvert \rvert ^2 - \lvert \lvert x \rvert \rvert ^2\, \right\rvert > \varepsilon \lvert \lvert x \rvert \rvert ^2 \, \right] \\ &= \mathbb{P}_{g \sim {\cal N}(0, I_{d})} \left[\, \left\lvert \frac{\,1}{d}\lvert \lvert x \rvert \rvert ^2 \cdot \lvert \lvert g \rvert \rvert ^2 - \lvert \lvert x \rvert \rvert ^2 \, \right\rvert >\varepsilon \lvert \lvert x \rvert \rvert ^2\, \right] \\ &= \mathbb{P}_{g \sim {\cal N}(0, I_d)} \left[ \,\left\lvert \,\lvert \lvert g \rvert \rvert ^2 - d\, \right\rvert > \varepsilon d\, \right] \end{align}$$ So we can apply our [[Concept Wiki/concentration inequality for magnitude of standard gaussian random vector]]! Since $\varepsilon<1$, we have $\varepsilon d<d$ and thus $\min \left\{ \frac{(\varepsilon d)^2}{d}, \varepsilon d \right\}=\varepsilon^2d$. Thus we have $$\begin{align} \mathbb{P}_{\hat{G} \sim {\cal N}\left( 0, \frac{1}{d} \right)^{\otimes d\times m}} \left[\,\left\lvert \,\lvert \lvert \hat{G}x \rvert \rvert^2 - \lvert \lvert x \rvert \rvert ^2 \, \right\rvert >\varepsilon \lvert \lvert x \rvert \rvert ^2\,\right] &\leq 2 \exp\left( -\frac{1}{8} \varepsilon^2d \right) \\ \implies \mathbb{P}_{\hat{G} \sim {\cal N}\left( 0, \frac{1}{d} \right)^{\otimes d\times m}} \left[\,(1-\varepsilon) \lvert \lvert x \rvert \rvert ^2 \leq\,\lvert \lvert \hat{G}x \rvert \rvert^2 \leq(1+\varepsilon)\lvert \lvert x \rvert \rvert ^2\,\right] &\geq 1 - 2\exp\left( -\frac{1}{8}\varepsilon^2d \right) \end{align}$$ Now, let $S_{ij}$ be the event that $(1-\varepsilon) \lvert \lvert x \rvert \rvert ^2 \leq\,\lvert \lvert \hat{G}x \rvert \rvert^2 \leq(1+\varepsilon)\lvert \lvert x \rvert \rvert ^2$ for $x=y_{i}-y_{j}$. Then by the [[Concept Wiki/outer measure has countable subadditivity\|union bound]], we have $$\begin{align} \mathbb{P}[S_{ij}^C \text{ for some }i,j] & \leq {n \choose 2} \cdot 2 \exp\left( \frac{1}{8} \varepsilon^2 d \right) \\ &\leq n^2 \exp\left( -\frac{1}{8} \varepsilon^2d \right) \\ &=\frac{1}{n} \exp\left( 3\log n-\frac{1}{8}\varepsilon^2\underbrace{ d }_{ d \geq 24 \frac{\log n}{\varepsilon^2}} \right) \\ \implies\quad &\leq \frac{1}{n} \exp\left( 3 \log n - 3\log n \right) \\ &=\frac{1}{n} \end{align}$$ $$\tag*{$\blacksquare$}$$

Note

Johnson-Lindenstrauss only deals with the pairwise distances between the $y_i$ and there are other aspects of the geometry that it does not address.

Despite this, it is an intuitive result and is still relevant to numerous applications.

Note

The proof of this lemma uses the first moment method

Extensions

It is easy to see that $(1-\epsilon )||y_i||\le ||f(y_i)||\le (1+\epsilon )||y_i||$ with the same probability bound by adding $\vec{0}$ to the collection of $y_i$ and increasing $n$ to $n+1$.

We can also write an expression for the bound on $d$ such that if $d\ge C(k)\frac{\log n}{{\epsilon }^2}$ then we can get a success probability of $1-\frac{1}{n^k}$.

Johnson-Lindenstrauss Transform

Johnson-Lindenstrauss Transform

Multiplying data by a random matrix that satisfies the criteria for the Johnson-Lindenstrauss lemma is sometimes called the Johnson-Lindnestrauss transform (JLT).

This is usually done for the purpose of dimensionality reduction.

There is also work being done to see how to speed up the multiplications $\hat{G}y$. The main approach to this is to find special matrices $\hat{G}$ that allow for faster matrix-vector multiplication.

• Simplest results deal with sparse matrices
• Also fast Fourier Transform via multiplication with the discrete Fourier transform matrix
  • multiply then subsample entries

Optimality

The result is not optimal. The original paper showed that dimension $\Omega (\log n)$ is required independent of $\epsilon$.

The following two papers show that the general result is tight up to constants:

• Kasper Green Larsen and Jelani Nelson. The johnson-lindenstrauss lemma is optimal for linear dimensionality reduction. arXiv preprint arXiv:1411.2404, 2014.
• Kasper Green Larsen and Jelani Nelson. Optimality of the johnson-lindenstrauss lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 633–638. IEEE, 2017.

References

References

See Also

Mentions

Mentions

TABLE mod as "Last Modified"
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link) OR contains(author, this.file.link) OR contains(director, this.file.link) OR contains(source, this.file.link), 1, "") AS direct_source
 
FLATTEN contains(type, "thought") AS is_thought
FLATTEN contains(tags, "dailynote") AS is_periodic
 
FLATTEN choice(length(modified) > 0, max(dateformat(modified, "yyyy-MM-dd")), file.mday) AS mod
 
WHERE !direct_source
    AND !is_thought
    AND !is_periodic
    AND file != this.file
 
SORT mod DESC
SORT file.name ASC

const { dateTime } = await cJS()
 
return function View() {
	const file = dc.useCurrentFile();
	return <p class="dv-modified">Created {dateTime.getCreated(file)}     ֍     Last Modified {dateTime.getLastMod(file)}</p>
}