dimension requirements for gaussian random matrix to be a restricted isometry with high probability

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

Suppose $k\ge 1$ and $\delta \in (0,1)$ and $d\ge 64\frac{k\log m}{{\delta }^2}$. Let $G\sim \mathcal{N}{\left(0,\frac{1}{d}\right)}^{\otimes d\times m}$. Then $\mathbb{P}[G\text{ has }(k,\delta )\text{-RIP}]\ge 1-\frac{2}{m^k}$

(We want to reduce the number of measurements required to ensure we can recover $x$ from only seeing $y=Gx$)

Proof

Suppose $S\subset [m],|S|=k$ and $x\in {\mathbb{R}}^m$. Define

1. $x^{(S)}\in {\mathbb{R}}^k$ as the restriction to indices in $S$

2. $G^{(S)}\in {\mathbb{R}}^{d\times k}$ be the restriction to columns with indices in $S$

If $||x|{|}_0\le k$ and all non-zero indices are in $S$, ie $\text{supp}(x)\subset S$, then we have $Gx=G^{(S)}{x}^{(S)}\text{ and }||x||=||x^{(S)}||$ In this case, the $(k,\delta )$ RIP is equivalent to requiring that (for all $S\subset [m]$ with $|S|=k$) we have $(1-\delta )||x^{(S)}|{|}^2\le ||G^{(S)}{x}^{(S)}|{|}^2\le (1+\delta )||x^{(S)}|{|}^2$ Now, let ${\hat{x}}^{(S)}:=\frac{x^{(S)}}{||x^{(S)}||}$. Then

\iff-\delta &\leq \hat{x}^{(S)}(G^{(S)T}G^{(S)} - I_{k})\hat{x}^{(S)} \leq \delta \\ \iff \lvert \lvert G^{(S)T}G^{(S)} -I_{k}\rvert \rvert &\leq\delta \end{align}$$

So, applying the union bound, we can see

\mathbb{P}[G \text{ not }(k,\delta)\text{-RIP}] &\leq_{\text{UB}} \sum_{S \subseteq[m], \lvert S \rvert =k} \mathbb{P}[\lvert \lvert G^{(S)T} G^{(S)} - I+k \rvert \rvert > \delta] \end{align}$$ Now, $\text{Law}(G^{(S)}) ={\cal N}\left( 0, \frac{1}{d} \right)^{\otimes d\times m}$. So introduce $H \sim {\cal N}(0, 1)^{\otimes k \times d}$. Then we have $$\begin{align} \mathbb{P}[G \text{ not }(k,\delta)\text{-RIP}] &\leq {{m}\choose{k}} \mathbb{P}[\lvert \lvert HH^T - dI_{k} \rvert \rvert >\delta d] \\ (*)&\leq {m\choose{k}} \cdot 2 \exp\left( -\frac{1}{8}\min \left\{ \frac{\delta^2d^2}{4d}, \frac{\delta d}{2} \right\} \right) \end{align}$$ Where we get $(*)$ from the [[Concept Wiki/high probability bound for operator norm of difference for Gaussian covariance matrix]] we saw [[School/Archived/Random Matrix Theory/02 Class Notes/Random Matrix Lecture 04#non-constructive-existence-of-nets\|last time]]. And continuing the calculation, we see $$\begin{align} \mathbb{P}[G \text{ not }(k,\delta)\text{-RIP}] &\leq m^k \cdot 2 \exp\left( -\frac{\delta^2}{32}d \right) \\ &=2\exp\left( k\log m-\frac{\delta^2}{32}d \right) \\ &\leq 2\exp(-k\log m) \\ &= \frac{2}{m^k} \end{align}$$ $$\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>
}