aboutsummaryrefslogtreecommitdiffstats
path: root/paper/sections/lowerbound.tex
diff options
context:
space:
mode:
authorThibaut Horel <thibaut.horel@gmail.com>2015-02-05 23:22:36 -0500
committerThibaut Horel <thibaut.horel@gmail.com>2015-02-05 23:22:36 -0500
commit190cd5633e7e3237be118c18d374b5542aa38be4 (patch)
treecec7f4bce86caa234585539657592821098da4d8 /paper/sections/lowerbound.tex
parent1b76bfe6f4c0335fcf04a9f683949a3d412e05cd (diff)
downloadcascades-190cd5633e7e3237be118c18d374b5542aa38be4.tar.gz
Polishing
Diffstat (limited to 'paper/sections/lowerbound.tex')
-rw-r--r--paper/sections/lowerbound.tex6
1 files changed, 3 insertions, 3 deletions
diff --git a/paper/sections/lowerbound.tex b/paper/sections/lowerbound.tex
index fdee069..b714766 100644
--- a/paper/sections/lowerbound.tex
+++ b/paper/sections/lowerbound.tex
@@ -1,5 +1,5 @@
In this section, we will consider the stable sparse recovery setting of
-Section~\ref{sec:relaxing}. Our goal is to obtain an information-theoretic
+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,
@@ -7,7 +7,7 @@ bipw11}
\begin{theorem}
\label{thm:lb}
- Let us consider a cascade model of the form XXX and a recovery algorithm
+ 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}$
(over the measurements):
@@ -19,7 +19,7 @@ bipw11}
= \Omega(s\log\frac{m}{s}/\log C)$.
\end{theorem}
-This theorem should be contrasted with Corollary~\ref{cor:relaxing}: up to an additive
+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.