fixed corollary 2

1 files changed, 6 insertions, 4 deletions

diff --git a/paper/sections/results.tex b/paper/sections/results.tex
index 96d79b9..7fbc25b 100644
--- a/paper/sections/results.tex
+++ b/paper/sections/results.tex
@@ -34,15 +34,17 @@ Assume that ${\bf (RE)}$ holds with $\gamma_n = n \gamma$ for $\gamma > 0$. Then
 \end{equation}
 \end{corollary}
 
+The following corollary follows trivially and gives the first $\Omega(s \log p)$ algorithm for graph reconstruction on general graphs.
+
 \begin{corollary}
-Suppose that after solving Eq.~\ref{eq:mle}, we construct the set $\hat {\cal S}_\eta := \{ i \in [1..p] : \hat \theta_i > \eta\}$ for $\eta > 0$. Suppose the number of measurements verifies:
+Assume that ${\bf (RE)}$ holds with $\gamma_n = n \gamma$ for $\gamma > 0$. Suppose that after solving Eq.~\ref{eq:mle}, we construct the set $\hat {\cal S}_\eta := \{ i \in [1..p] : \hat \theta_i > \eta\}$ for $\eta > 0$. Suppose the number of measurements verifies:
 \begin{equation}
-n > \frac{4}{\gamma^2 p_{\min}} s \log p
+n > \frac{4}{\gamma^2 p_{\min} \eta^2} s \log p
 \end{equation}
-Then $\hat {\cal S}_\eta = {\cal S}^*_{2\eta}$, where ${\cal S}^*_{2\eta} = \{ i \in [1..p] :\theta^*_i > 2 \eta \} $. In other words, we incur no false positives (false parents) and recover all `strong' parents, such that $\theta^*_j > 2 \eta$.
+Then $\hat {\cal S}_\eta = {\cal S}^*_{2\eta}$, where ${\cal S}^*_{2\eta} = \{ i \in [1..p] :\theta^*_i > 2 \eta \} $. In other words, we incur no false positives (false parents) and recover all `strong' parents, such that $\theta^*_j > 2 \eta$. 
 \end{corollary}
 
-Note that here $n$ is the number of measurements and not the number of cascades. This is an important improvement over prior work since we expect several measurements per cascade. We claim that graph recovery is better understood as a function of $n$, the cumulative number of steps in each cascade, rather than as a function $N$, the number of individual cascades.
+Notice that by choosing $\eta < \frac{p_{\min}}{2}$, we recover all parents exactly. Note that $n$ is the number of measurements and not the number of cascades. This is an important improvement over prior work since we expect several measurements per cascade. We claim that graph recovery is better understood as a function of $n$, the cumulative number of steps in each cascade, rather than as a function $N$, the number of individual cascades.
 
 Unfortunately, proving the {\bf (RE)} assumption for correlated measurements is highly non-trivial. We can show a very crude ${\cal O}(N)$-lower bound for $\gamma_n$ by exploiting only the first set of measurements, where only the source nodes are active. Note that even though we waste a lot of information, we obtain similar asymptotic behavior than previous work.