From 553511259bdd50dc9df89f52893861a6c4332d79 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Fri, 6 Feb 2015 01:43:15 -0500
Subject: More polishing

---
 paper/sections/lowerbound.tex | 92 ++++++++++++++++++++++++-------------------
 1 file changed, 51 insertions(+), 41 deletions(-)

(limited to 'paper/sections/lowerbound.tex')

diff --git a/paper/sections/lowerbound.tex b/paper/sections/lowerbound.tex
index b714766..7f51f46 100644
--- a/paper/sections/lowerbound.tex
+++ b/paper/sections/lowerbound.tex
@@ -1,63 +1,61 @@
-In this section, we will consider the stable sparse recovery setting of
-Section~\ref{sec:relaxing_sparsity}.  Our goal is to obtain an information-theoretic
-lower bound on the number of measurements necessary to approximately recover
-the parameter $\theta$ of a cascade model from observed cascades. Similar lower
-bounds were obtained for sparse linear inverse problems in \cite{pw11, pw12,
-bipw11}
+In \cite{Netrapalli:2012}, the authors explicitate a lower bound of
+$\Omega(s\log\frac{n}{s})$ on the number of cascades necessary to achieve good
+support recovery with constant probability under a \emph{correlation decay}
+assumption.  In this section, we will consider the stable sparse recovery
+setting of Section~\ref{sec:relaxing_sparsity}.  Our goal is to obtain an
+information-theoretic lower bound on the number of measurements necessary to
+approximately recover the parameter $\theta$ of a cascade model from observed
+cascades. Similar lower bounds were obtained for sparse \emph{linear} inverse
+problems in \cite{pw11, pw12, bipw11}.
 
 \begin{theorem}
     \label{thm:lb}
     Let us consider a cascade model of the form \eqref{eq:glm} and a recovery algorithm
     $\mathcal{A}$ which takes as input $n$ random cascade measurements and
-    outputs $\hat{\theta}$ such that with probability $\delta<\frac{1}{2}$
+    outputs $\hat{\theta}$ such that with probability $\delta>\frac{1}{2}$
     (over the measurements):
-    \begin{displaymath}
+    \begin{equation}
+        \label{eq:lb}
         \|\hat{\theta}-\theta^*\|_2\leq
         C\min_{\|\theta\|_0\leq s}\|\theta-\theta^*\|_2
-    \end{displaymath}
-    where $\theta^*$ is the true paramter of the cascade model. Then $n
+    \end{equation}
+    where $\theta^*$ is the true parameter of the cascade model. Then $n
     = \Omega(s\log\frac{m}{s}/\log C)$.
 \end{theorem}
 
 This theorem should be contrasted with Theorem~\ref{thm:approx_sparse}: up to an additive
 $s\log s$ factor, the number of measurements required by our algorithm is
-tight.
+tight.  The proof of Theorem~\ref{thm:lb} follows an approach similar to \cite{pw12}.
+We only present a sketch of the proof here and refer the reader to their paper
+for more details.
 
-The proof of Theorem~\ref{thm:lb} follows an approach similar to \cite{pw12}.
-Let us consider an algorithm $\mathcal{A}$ as in the theorem. Intuitively,
-$\mathcal{A}$ allows Alice and Bob to send $\Omega(s\log\frac{m}{s})$ quantity
-of information over a Gaussian channel. By the Shannon-Hartley theorem, this
-quantity of information is $O(n\log C)$.  These two bounds together give the
-theorem.
+Let us consider an algorithm $\mathcal{A}$ which verifies the recovery
+guarantee of Theorem~\ref{thm:lb}: there exists a probability distribution over
+measurements such that for all vectors $\theta^*$, \eqref{eq:lb} holds w.p.
+$\delta$. This implies by the probabilistic method that for all distribution
+$D$ over vectors $\theta$, there exists an $n\times m$ measurement matrix $X_D$ with
+such that \eqref{eq:lb} holds w.p. $\delta$ ($\theta$ is now the
+random variable).
 
-Formally, let $\mathcal{F}\subset \{S\subset [1..m]\,|\, |S|=s\}$ be a family
-of $s$-sparse supports such that:
-\begin{itemize}
-    \item $|S\Delta S'|\geq s$ for $S\neq S'\in\mathcal{F}$ .
-    \item $\P_{S\in\mathcal{F}}[i\in S]=\frac{s}{m}$ for all $i\in [1..m]$ and
-        when $S$ is chosen uniformly at random in $\mathcal{F}$
-    \item $\log|\mathcal{F}| = \Omega(s\log\frac{m}{s})$
-\end{itemize}
-such a family can be obtained by considering a linear code (see details in
-\cite{pw11}. Let $X = \big\{t\in\{-1,0,1\}^m\,|\, \mathrm{supp}(t)\in\mathcal{F}\big\}$. 
+Consider the following distribution $D$: choose $S$
+uniformly at random from a ``well-chosen'' set of $s$-sparse supports
+$\mathcal{F}$ and $t$ uniformly at random from $X
+\defeq\big\{t\in\{-1,0,1\}^m\,|\, \mathrm{supp}(t)\in\mathcal{F}\big\}$. Define
+$\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.
+Consider the following communication game between Alice and Bob:
 \begin{itemize}
-    \item Alice chooses $S$ uniformly at random from $\mathcal{F}$ and
-        $t$ uniformly at random from $X$ subject to $\mathrm{supp}(x) = S$
-    \item Let $w\sim\mathcal{N}(0, \alpha \frac{s}{m}I_m)$ and $\theta
-        = t + w$. Since for all $\theta$, $\mathcal{A}$ recovers $\theta$ with
-        probability $1-\delta$ over the measurements, there exists a fixed set
-        of measurements $x_1,\ldots, x_n$ such that with probability
-        $1-\delta$ over $\theta$, $\mathcal{A}$ recovers $\theta$. Alice sends
-        those measurements to Bob.
-    \item Bob uses $\mathcal{A}$ to recover $\hat{\theta}$ from the
-        measurements, then computes $\hat{t}$ the best $\ell_2$ approximation
-        of $\hat{\theta}$ in $X$.
+    \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$.
 \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
+theorem, this information is also
+upper-bounded by $\O(n\log C)$. These two bounds together imply the theorem.
 
-We have the following from \cite{pw11} and \cite{pw12} respectively.
-
+\begin{comment}
 \begin{lemma}
     \label{lemma:upperinf}
     Let $S'=\mathrm{supp}(\hat{t})$. If $\alpha = \Omega(\frac{1}{C})$, $I(S, S')
@@ -71,3 +69,15 @@ We have the following from \cite{pw11} and \cite{pw12} respectively.
 
 Lemmas \ref{lemma:lowerinf} and \ref{lemma:upperinf} together give Theorem
 \ref{thm:lb}.
+
+Formally, let $\mathcal{F}\subset \{S\subset [1..m]\,|\, |S|=s\}$ be a family
+of $s$-sparse supports such that:
+\begin{itemize}
+    \item $|S\Delta S'|\geq s$ for $S\neq S'\in\mathcal{F}$ .
+    \item $\P_{S\in\mathcal{F}}[i\in S]=\frac{s}{m}$ for all $i\in [1..m]$ and
+        when $S$ is chosen uniformly at random in $\mathcal{F}$
+    \item $\log|\mathcal{F}| = \Omega(s\log\frac{m}{s})$
+\end{itemize}
+such a family can be obtained by considering a linear code (see details in
+\cite{pw11}. Let . 
+\end{comment}
-- 
cgit v1.2.3-70-g09d2

