aboutsummaryrefslogtreecommitdiffstats
path: root/paper/sections/lowerbound.tex
diff options
context:
space:
mode:
authorThibaut Horel <thibaut.horel@gmail.com>2015-02-06 15:24:51 -0500
committerThibaut Horel <thibaut.horel@gmail.com>2015-02-06 15:24:51 -0500
commit07a4bc620e7056e8ef0e21102794d4cb80044f82 (patch)
tree558d6de317d9c040b0c584cb9f6d3f1f08fc0820 /paper/sections/lowerbound.tex
parent748e4be47ca0e6ee8dccdeb905834dc0c7ddd6b6 (diff)
downloadcascades-07a4bc620e7056e8ef0e21102794d4cb80044f82.tar.gz
Compression
Diffstat (limited to 'paper/sections/lowerbound.tex')
-rw-r--r--paper/sections/lowerbound.tex7
1 files changed, 2 insertions, 5 deletions
diff --git a/paper/sections/lowerbound.tex b/paper/sections/lowerbound.tex
index 5c35446..ed3600f 100644
--- a/paper/sections/lowerbound.tex
+++ b/paper/sections/lowerbound.tex
@@ -44,11 +44,8 @@ $\mathcal{F}$ and $t$ uniformly at random from $X
$\theta = t + w$ where $w\sim\mathcal{N}(0, \alpha\frac{s}{m}I_m)$ and $\alpha
= \Omega(\frac{1}{C})$.
-Consider the following communication game between Alice and Bob:
-\begin{itemize}
- \item Alice sends $y\in\reals^m$ drawn from a Bernouilli distribution of parameter
- $f(X_D\theta)$ to Bob.
- \item Bob uses $\mathcal{A}$ to recover $\hat{\theta}$ from $y$.
+Consider the following communication game between Alice and Bob: \emph{(1)} Alice sends $y\in\reals^m$ drawn from a Bernouilli distribution of parameter
+$f(X_D\theta)$ to Bob. \emph{(2)} Bob uses $\mathcal{A}$ to recover $\hat{\theta}$ from $y$.
\end{itemize}
It can be shown that at the end of the game Bob now has a quantity of
information $\Omega(s\log \frac{m}{s})$ about $S$. By the Shannon-Hartley