diff options
Diffstat (limited to 'paper/sections/lowerbound.tex')
| -rw-r--r-- | paper/sections/lowerbound.tex | 6 |
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. |