From aca39c2f4cc95566d7bfb671a976cfd785dac42b Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sun, 1 Feb 2015 18:23:15 -0500
Subject: Intro: fix typos

---
 paper/sections/intro.tex | 30 ++++++++++++++----------------
 1 file changed, 14 insertions(+), 16 deletions(-)

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

diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex
index b84f562..695c084 100644
--- a/paper/sections/intro.tex
+++ b/paper/sections/intro.tex
@@ -18,34 +18,32 @@ the parameters of the cascade model. This problem is known in the literature as
 the \emph{Graph Inference problem}.
 
 More precisely, solving the Graph Inference problem involves designing
-an algorithm taking as input as set of observed cascades (realisations of the
+an algorithm taking as input a set of observed cascades (realisations of the
 diffusion process) and recovers with high probability a large fraction of the
-graph edges. The goal is then to understand the relationship between the number
+graph's edges. The goal is then to understand the relationship between the number
 of observations, the probability of success, and the accuracy of the
 reconstruction.
 
-In most cases, the Graph Inference problem can be decomposed and analyzed
-``node-by-node''. In this introduction, we will thus focus on a single node of
-degree $s$ and discuss how to identify its parents among the $m$ nodes of the
-graph. Prior work has shown that the typical required number of observed
-cascades is $\O(poly(s)\log m)$.
+The Graph Inference problem can be decomposed and analyzed ``node-by-node''.
+Thus, we will focus on a single node of degree $s$ and discuss how to identify
+its parents among the $m$ nodes of the graph. Prior work has shown that the
+required number of observed cascades is $\O(poly(s)\log m)$.
 
 A more recent line of research has focused on applying advances on sparse
-inverse problems to the graph inference problem. Indeed, the graph can be
-interpreted as a ``sparse signal'' that is sensed through influence cascades
-and then recovered. The challenge is that influence cascade models typically
-lead to non-linear inverse problems. The sparse recovery literature
-suggests that $\Omega(s\log\frac{m}{s})$ cascade observations should be
-sufficient to recover the graph. However, the best known upper bound to this
-day is $\O(s^2\log m)$.
+recovery to the graph inference problem. Indeed, the graph can be interpreted
+as a ``sparse signal'' measured through influence cascades and then recovered.
+The challenge is that influence cascade models typically lead to non-linear
+inverse problems. The sparse recovery literature suggests that
+$\Omega(s\log\frac{m}{s})$ cascade observations should be sufficient to recover
+the graph. However, the best known upper bound to this day is $\O(s^2\log m)$.
 
 The contributions of this paper are the following:
 \begin{itemize}
     \item we formulate the Graph Inference problem in the context of
-        discrete-time influence cascades as a sparse inverse problem for
+        discrete-time influence cascades as a sparse recovery problem for
         a specific type of Generalized Linear Model. This formulation notably
         encompases the well-studied Independent Cascade Model and Voter Model.
-    \item we give a an algorithm which recovers the graph edges using $\O(s\log
+    \item we give an algorithm which recovers the graph's edges using $\O(s\log
         m)$ cascades. Furthermore, we show that our algorithm is also able to
         recover the edge weights (the parameters of the influence model),
         a problem which has been seemingly overlooked so far.
-- 
cgit v1.2.3-70-g09d2

