high probability bound on singular values of gaussian random 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);
}
 
 

(all is with high probability)

Corollary

Let $G\in {\mathbb{R}}^{d\times m}$ be a Gaussian random matrix with $d\le m$. Then $\mathbb{P}[\sqrt{m}-64\sqrt{d}\le {\sigma }_d(G)\le \cdots \le {\sigma }_1(G)\le \sqrt{m}+32\sqrt{d}]>1-2\exp (-d)$

$\sqrt{m}\pm \mathcal{O}(\sqrt{d})$==}

ie all singular values are {==

NOTE

This is a good event; we want this to happen. And luckily, we have high probability for this event.

We showed the probability for this event already, so now, assuming the event happens, we just need to prove the bound.

Proof

Recall $\sqrt{\cdot }$) yields

First-order Taylor approximation (and concavity of

\sqrt{ 1+x } &\leq 1+\frac{x}{2}\quad &\text{for } x \geq 0 \\ \sqrt{ 1-x } &\geq 1-x \quad &\text{for } 0\leq x\leq 1 \end{align}$$

If the event for our high probability bound for operator norm of difference for Gaussian covariance matrix happens, then we have $||\Delta ||=||G{G}^T-m{I}_d||\le 64\sqrt{dm}$

ie if the event happens, we have (1)

\sigma_{1}(G) = \lvert \lvert G \rvert \rvert &= \sqrt{ \lvert \lvert GG^T \rvert \rvert } \\ (*)&\leq \sqrt{ \lvert \lvert mI_{d} \rvert \rvert + \lvert \lvert \Delta \rvert \rvert } \\ &\leq \sqrt{ m + 64\sqrt{ dm } } \\ &= \sqrt{ m }\sqrt{ 1 + 64\sqrt{ \frac{d}{m} } } \\ (**)&\leq\sqrt{ m }\left( 1+\frac{64}{2}\sqrt{ \frac{d}{m} } \right) \\ &= \sqrt{ m } + 32\sqrt{ d } \end{align}$$ Where - $(*)$ is from our [[Concept Wiki/Weyl's Theorem#special-case-for-random-matrix\|special case of Weyl]] - $(**)$ is from the first of our two bounds above Then, for $\sigma_{d}(G)$, we have a similar bound. Note that if $m-64\sqrt{ dm } <0$, then $\sqrt{ m }-64\sqrt{ d }<0$ and the result follows. So suppose $m-64\sqrt{ dm } \geq 0$. (2) $$\begin{align} \sigma_{d}(G) &= \sqrt{ \lambda_{d}(GG^T) } \\ (*)&\geq \sqrt{ \lambda_{d}(mI_{d}) - \lvert \lvert \Delta \rvert \rvert } \\ &\geq \sqrt{ m-64\sqrt{ dm } } \\ &= \sqrt{ m }\sqrt{ 1-64\sqrt{ \frac{d}{m} } } \\ (* *)&\geq \sqrt{ m }\left( 1-64 \sqrt{ \frac{d}{m} } \right) \\ &= \sqrt{ m } - 64\sqrt{ d } \end{align}$$ Where - $(*)$ is from our [[Concept Wiki/Weyl's Theorem#special-case-for-random-matrix\|special case of Weyl]] - $(* *)$ is from the second of our two bounds above $$\tag*{$\blacksquare$}$$

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