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

[[concept]]

[!themes] Topics

Evaluation Error: SyntaxError: Unexpected token '>'

at DataviewInlineApi.eval (plugin:dataview:19027:21)

at evalInContext (plugin:dataview:19028:7)

at asyncEvalInContext (plugin:dataview:19038:32)

at DataviewJSRenderer.render (plugin:dataview:19064:19)

at DataviewJSRenderer.onload (plugin:dataview:18606:14)

at DataviewJSRenderer.load (app://obsidian.md/app.js:1:1182416)

at DataviewApi.executeJs (plugin:dataview:19607:18)

at DataviewCompiler.eval (plugin:digitalgarden:10763:23)

at Generator.next (<anonymous>)

at fulfilled (plugin:digitalgarden:77:24)

Theorem

Suppose $k \geq 1$ and $δ \in (0, 1)$ and $d \geq 64 \frac{k \log m}{δ^{2}}$ . Let $G \sim N {(0, \frac{1}{d})}^{\otimes d \times m}$ . Then

P [G has (k, δ) -RIP] \geq 1 - \frac{2}{m^{k}}

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

Proof

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

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

If $| | x | |_{0} \leq k$ and all non-zero indices are in $S$ , ie $supp (x) \subset S$ , then we have
$G x = G^{(S)} x^{(S)} and | | x | | = | | x^{(S)} | |$
In this case, the $(k, δ)$ RIP is equivalent to requiring that
(for all $S \subset [m]$ with $| S | = k$ ) we have
$(1-\delta)\lvert \lvert x^{(S)} \rvert \rvert {#2} \leq \lvert \lvert G^{(S)}x^{(S)} \rvert \rvert {#2} \leq (1+\delta) \lvert \lvert x^{(S)} \rvert \rvert {#2}$

Now, let ${\hat{x}}^{(S)} := \frac{x^{(S)}}{| | x^{(S)} | |}$ . Then
$\begin{aligned} ⟺ - δ & \leq {\hat{x}}^{(S)} (G^{(S) T} G^{(S)} - I_{k}) {\hat{x}}^{(S)} \leq δ \\ ⟺ | | G^{(S) T} G^{(S)} - I_{k} | | & \leq δ \end{aligned}$

So, applying the union bound, we can see
$\begin{aligned} P [G not (k, δ) -RIP] & \leq_{UB} \sum_{S \subseteq [m], | S | = k} P [| | G^{(S) T} G^{(S)} - I + k | | > δ] \end{aligned}$
Now, $Law (G^{(S)}) = N {(0, \frac{1}{d})}^{\otimes d \times m}$ . So introduce $H \sim N (0, 1)^{\otimes k \times d}$ . Then we have
$\begin{aligned} P [G not (k, δ) -RIP] & \leq (\binom{m}{k}) P [| | H H^{T} - d I_{k} | | > δ d] \\ (*) & \leq (\binom{m}{k}) \cdot 2 \exp (- \frac{1}{8} min {\frac{δ^{2} d^{2}}{4 d}, \frac{δ d}{2}}) \end{aligned}$
Where we get $(*)$ from the high probability bound for operator norm of difference for Gaussian covariance matrix we saw last time. And continuing the calculation, we see
$\begin{aligned} P [G not (k, δ) -RIP] & \leq m^{k} \cdot 2 \exp (- \frac{δ^{2}}{32} d) \\ = 2 \exp (k \log m - \frac{δ^{2}}{32} d) \\ \leq 2 \exp (- k \log m) \\ = \frac{2}{m^{k}} \end{aligned}$ $\begin{matrix} ◼ \end{matrix}$

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

References

See Also

Mentions