high probability bound on singular values of gaussian random matrix

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

Proof

Recall

First-order Taylor approximation (and concavity of $\sqrt{\cdot}$ ) yields

\begin{aligned} \sqrt{1 + x} & \leq 1 + \frac{x}{2} & for x \geq 0 \\ \sqrt{1 - x} & \geq 1 - x & for 0 \leq x \leq 1 \end{aligned}

If the event for our high probability bound for operator norm of difference for Gaussian covariance matrix happens, then we have

| | Δ | | = | | G G^{T} - m I_{d} | | \leq 64 \sqrt{d m}

ie if the event happens, we have
(1)

\begin{aligned} σ_{1} (G) = | | G | | & = \sqrt{| | G G^{T} | |} \\ (*) & \leq \sqrt{| | m I_{d} | | + | | Δ | |} \\ \leq \sqrt{m + 64 \sqrt{d m}} \\ = \sqrt{m} \sqrt{1 + 64 \sqrt{\frac{d}{m}}} \\ (* *) & \leq \sqrt{m} (1 + \frac{64}{2} \sqrt{\frac{d}{m}}) \\ = \sqrt{m} + 32 \sqrt{d} \end{aligned}

Where

$(*)$ is from our special case of Weyl
$(* *)$ is from the first of our two bounds above

Then, for $σ_{d} (G)$ , we have a similar bound.

Note that if $m - 64 \sqrt{d m} < 0$ , then $\sqrt{m} - 64 \sqrt{d} < 0$ and the result follows. So suppose $m - 64 \sqrt{d m} \geq 0$ .

(2)

\begin{aligned} σ_{d} (G) & = \sqrt{λ_{d} (G G^{T})} \\ (*) & \geq \sqrt{λ_{d} (m I_{d}) - | | Δ | |} \\ \geq \sqrt{m - 64 \sqrt{d m}} \\ = \sqrt{m} \sqrt{1 - 64 \sqrt{\frac{d}{m}}} \\ (* *) & \geq \sqrt{m} (1 - 64 \sqrt{\frac{d}{m}}) \\ = \sqrt{m} - 64 \sqrt{d} \end{aligned}

Where

$(*)$ is from our special case of Weyl
$(* *)$ is from the second of our two bounds above

\begin{matrix} ◼ \end{matrix}

References

See Also

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