high probability bound for operator norm of difference for Gaussian covariance matrix

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

For$d<m$, let $G\sim N(0,1{)}^{\otimes d\times m}$. Define $\Delta :=G{G}^T-m{I}_d$. Then

\mathbb{P}[\lvert \lvert \Delta \rvert \rvert \geq 64\sqrt{ dm }] &\leq 2\exp(-d) \\ \text{and }\lvert \lvert G \rvert \rvert ^2=\lvert \lvert GG^T \rvert \rvert &\leq m+{\cal O}(\sqrt{ dm }) \end{align}$$

Proof

Let $\epsilon :=\frac{1}{4}$. Then we have:

1. There exists an epsilon net $\mathcal{X}$ of $B^d$ where $|\mathcal{X}|\le {\left(1+\frac{2}{\epsilon }\right)}^d={\left(1+\frac{2}{\frac{1}{4}}\right)}^d=9^d$
2. We have the bound (from epsilon net restricted inner product bounds the operator norm) $||\Delta ||\le \frac{1}{1-2\epsilon }||\Delta |{|}_{\mathcal{X}}=\frac{1}{1-2\left(\frac{1}{4}\right)}||\Delta |{|}_{\mathcal{X}}=2||\Delta |{|}_{\mathcal{X}}$

So

\mathbb{P}[\lvert \lvert \Delta \rvert \rvert \geq t] &\leq \mathbb{P}\left[ \lvert \lvert \Delta \rvert \rvert _{{\cal X}} \geq \frac{t}{2} \right] \\ \text{union bound} \implies &\leq \sum_{x \in{\cal X}} \mathbb{P}\left[ \underbrace{\lvert x^T\Delta x \rvert}_{GG^T - mI_{d}} \geq \frac{t}{2} \right] \\ \text{Since } x \in {\cal X} \subseteq B^d &\text{ we know } \lvert \lvert x \rvert \rvert \leq 1. \text{ So let } \hat{x}:= \frac{x}{\lvert \lvert x \rvert \rvert} \in \mathbb{S}^{d-1}\\ \\ \implies&\leq \sum_{x \in {\cal X}} \mathbb{P}\left[ \lvert \hat{x}^T \Delta \hat{x} \rvert \geq \frac{t}{2} \right] \\ &= \sum_{x \in {\cal X}} \mathbb{P}_{G}\left[ \lvert\,\lvert \lvert \underbrace{G^T\hat{x}}_{\in \mathbb{R}^m,\, \text{Law}=N(0,I_{m})} \rvert \rvert^2 - m \,\rvert \geq \frac{t}{2} \right] \\ \text{Now let }g&=G^T\hat{x} \\ \implies &= \lvert {\cal X} \rvert \cdot \mathbb{P}_{g \sim N(0, I_{m})}\left[ \lvert\,\lvert \lvert g \rvert \rvert ^2 -m \,\rvert \geq \frac{t}{2} \right] \\ &\leq 9^d\cdot 2\exp\left( -\frac{1}{8}\min\left\{ \frac{t^2}{4m}, \frac{t}{2} \right\} \right) \\ &\leq 2\exp\left( 3d - \frac{1}{8} \min\left\{ \frac{C^2}{4}d, \underbrace{\frac{C}{2}\sqrt{ dm }}_{d\leq m \implies \sqrt{ dm } \geq d} \right\} \right) \\ [\text{set } t:= C\sqrt{ dm },\;9 \leq \exp(3)] \implies &\leq 2\exp\left( d\left[ 3- \underbrace{\min\left\{ \frac{C^2}{32}, \frac{C}{16} \right\}}_{C=64\to \min(>4, 4)} \right] \right) \\ (*) C:= 64 \to\quad&\leq 2 \exp(-d) \end{align}$$ For $(*)$, we want to pick $C$ big enough that everything is negative. $$\tag*{$\blacksquare$}$$

Union Bound

the union bound is countable subadditivity or the fact that $\mathbb{P}\left({\bigcup }_i{A}_i\right)\le {\sum }_i\mathbb{P}(A_i)$

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