diff options
| author | Thibaut Horel <thibaut.horel@gmail.com> | 2015-02-05 23:22:36 -0500 |
|---|---|---|
| committer | Thibaut Horel <thibaut.horel@gmail.com> | 2015-02-05 23:22:36 -0500 |
| commit | 190cd5633e7e3237be118c18d374b5542aa38be4 (patch) | |
| tree | cec7f4bce86caa234585539657592821098da4d8 /paper/sections/lowerbound.tex | |
| parent | 1b76bfe6f4c0335fcf04a9f683949a3d412e05cd (diff) | |
| download | cascades-190cd5633e7e3237be118c18d374b5542aa38be4.tar.gz | |
Polishing
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. |
