normalized gaussian random matrix preserves geometry in expectation

[[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);
}
 
 

Important

Let $G\sim \mathcal{N}(0,1{)}^{\otimes d\times m}$ and $Y\in {\mathbb{R}}^{m\times n}$. Now, define $\hat{G}:=\frac{1}{\sqrt{d}}G,\text{Law}(\hat{G})=\mathcal{N}{\left(0,\frac{1}{d}\right)}^{\otimes d\times m}$ Then

\mathbb{E}[\,\lvert \lvert \hat{G}y \rvert \rvert ^2\,] &= \lvert \lvert y \rvert \rvert ^2 \\ \mathbb{E}[\,\langle \hat{G}y_{1}, \hat{G}y_{2} \rangle \,] &= \langle y_{1}, y_{2} \rangle \\ \mathbb{E}\left[ \,(\hat{G}Y)^{\intercal}(\hat{G}Y)\, \right] &= Y^{\intercal}Y \end{align}$$ ie, in expectation, $\hat{G}$ preserves the lengths, angles, and [[Concept Wiki/Gram matrix\|Gram matrices]]. That is, it preserves all the geometry of $\mathbb{R}^m$

Line of Reasoning

Note that for any column of $Y$, say $y=y_i$, we have

Expected Magnitude

\mathbb{E}[\lvert \lvert Gy \rvert \rvert ^2] &= \mathrm{Tr}(\text{Cov}(Gy) ) \\ &= d \lvert \lvert y \rvert \rvert ^2 \end{align}$$

and for any $y_1,y_2$ columns of $Y$

Expected Direction

\mathbb{E}[\langle Gy_{1}, Gy_{2} \rangle] &= \mathrm{Tr}(\text{Cov}(Gy_{1}, Gy_{2}) ) \\ &= d\langle y_{1},y_{2} \rangle \end{align}$$

And, looking at the Gram matrix,

Expected Gram Matrix $\mathbb{E}\left[(GY{)}^{⊺}(GY)\right]=d{Y}^{⊺}Y$

Caveats

NOTE

Note that this holds for any $d$, including $d\ll m$ and $d=1$. This is because we are taking expectations.

If $y$ is selected first before we realize $\hat{G}$, then we hope that $||\hat{G}y||$ will concentrate about $||y||$. Our calculations for the joint show that $\text{Law}(\hat{G}y)=\mathcal{N}\left(0,\frac{1}{d}||y|{|}^2{I}_d\right)$ So (with rescaling, obviously), our concentration inequality for magnitude of standard gaussian random vector holds and we should see the desired behavior.

If $y$ does not depend on $\hat{G}$

Assuming we ensure $\hat{G}\perp y$, the probability of actually preserving geometry depends on $d$.

$d=1$, then $\hat{G}=g^{⊺}$ for some $g\in \mathcal{N}(0,I_d)$. We still have $\mathbb{E}[||\hat{G}{y}_i|{|}^2]=\mathbb{E}[⟨g,y_i{⟩}^2]=||y_i|{|}^2$ But clearly $⟨g,y_i{⟩}^2\approx ||y_i|{|}^2$ cannot hold simultaneously for many $y_i$ regardless of if we choose them before realizing $\hat{G}$.

If

Exercise

Construct some examples of this case

If $y$ depends on $\hat{G}$...

If $d\ll m$, then once $\hat{G}$ is realized, we can pick $y\in \text{Null}(\hat{G})$ so that $0=||\hat{G}y||\ll ||y||$.

• In this case, $\hat{G}$ will not preserve the geometry of arbitrary vectors $y$.
• In particular, we can find vectors $y$ that depend on $\hat{G}$ such that the geometry is badly distorted.

Review

rmt

Normalized gaussian random matrices preserve geometry (in expectation), BUT

Assuming we ensure $\hat{G}\perp y$, the probability of {1||preserving geometry} depends on {==2||the “output” dimension $d$==}.

For $\hat{G}\sim \mathcal{N}{\left(0,\frac{1}{d}\right)}^{\otimes d\times m}$ and $y\in {\mathbb{R}}^m$, what is the (co)variance matrix of $\hat{G}y$? -?- $\frac{1}{d}||y|{|}^2{I}_d$

If $\hat{G}\sim \mathcal{N}{\left(0,\frac{1}{d}\right)}^{\otimes d\times m}$, why do we need $y\in {\mathbb{R}}^m$ to be independent of $\hat{G}$ to preserve geometry if $d<m$? -?- Otherwise, we can choose $y\in \text{Null}(\hat{G})$ and then the norm is not preserved.

References

References

See Also

Mentions

Mentions

const modules = await cJS()
 
const COLUMNS = [  
	{ id: "Name", value: page => page.$link },  
	{ id: "Last Modified", value: page => modules.dateTime.getLastMod(page) },
];  
  
return function View() {  
	const current = dc.useCurrentFile();
// Selecting `#game` pages, for example. 
	let queryString = `@page and linksto(${current.$link})`;
	let pages = dc.useQuery(queryString);
	
	// check types
	pages = pages.filter( (p) => !modules.typeCheck.checkAll(p, current) ).sort()
	
	
	return <dc.Table columns={COLUMNS} rows={pages} paging={20}/>;  
}  

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>
}