small changes

2 files changed, 12 insertions, 9 deletions

diff --git a/paper/sections/assumptions.tex b/paper/sections/assumptions.tex
index a697d38..cff1051 100644
--- a/paper/sections/assumptions.tex
+++ b/paper/sections/assumptions.tex
@@ -1,11 +1,16 @@
+In this section, we compare the main assumption of \cite{Daneshmand:2014}, commonly known as the {\it irrepresentability condition}, to the restricted eigenvalue condition. We argue that the restricted eigenvalue is weaker and more likely to hold in practical situations.
+
 \subsection{The Irrepresentability Condition}
 
-\cite{Daneshmand:2014} rely on an `incoherence' condition on the hessian of the likelihood function. It is in fact easy to see that their condition is equivalent to the more commonly called {\it (S, s)-irrepresentability} condition:
+\cite{Daneshmand:2014} rely on an `incoherence' condition on the hessian of the likelihood function. It is in fact easy to see that their condition is equivalent to the more commonly called {\it (S,s)-irrepresentability} condition:
 
 \begin{definition}
-Following similar notation, let $Q^* \nabla^2 f(\theta^*)$. Let $Q_{S^C,S} XXX$, the {\it (S, s)-irrepresentability} condition is defined as:
+Following similar notation, let $Q^* \defeq \nabla^2 f(\theta^*)$. Let $S$ and $S^c$ be the set of indices of all the parents and non-parents respectively and $Q_{S,S}$, $Q_{S^c,S}$, $Q_{S, S^c}$, and $Q_{S^c, S^c}$ the induced sub-matrices.
+
+
+The {\it (S,s)-irrepresentability} condition is defined as:
 \begin{equation}
-blabla
+\nu_{\text{irrepresentable}}(S) \defeq \max_{\tau \in \mathbb{R}^p \ :\ \| \tau \|_{\infty} \leq 1} \|Q_{S^c, S} Q_{S, S}^{-1} \tau\|_{\infty}
 \end{equation}
 \end{definition}
 
diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex
index d2db035..f7a187c 100644
--- a/paper/sections/intro.tex
+++ b/paper/sections/intro.tex
@@ -1,12 +1,10 @@
-A recent line of research has focused on applying advances in sparse recovery to graph analysis. A graph can be interpreted as a signal that one seeks to `compress' or `sketch' and then `recovered'. However, we could also consider the situation where the graph is unknown to us, and we dispose of few measurements to recover the signal. Which kind of measurements do we dispose of in practice?
+A recent line of research has focused on applying advances in sparse recovery to graph analysis. A graph can be interpreted as a signal that one seeks to `compress' or `sketch' and then `recovered'. However, we could also consider the situation where the graph is unknown to us, and we dispose of few measurements to recover the signal. Which real-life processes allow us to `measure' the graph?
 
-A diffusion process on a graph, which depends on the edges and edge weights in the graph, provides valuable information. By observing the sequence of nodes which become `infected' over time without knowledge of who has `influenced' whom, can we recover the graph on which this process takes place? The spread of a particular behavior through a network is known as an {\it Influence Cascade}. In this context, the {\it Graph Inference} problem is to recover the edges of the graph from the observation of few influence cascades. We propose to show how sparse recovery can be applied to solve this recently introduced graph inference problem.
+A diffusion process taking place on a graph can provide valuable information about the existence of edges and their edge weights. By observing the sequence of nodes which become `infected' over time without knowledge of who has `infected' whom, can we recover the graph on which the process takes place? The spread of a particular behavior through a network is known as an {\it Influence Cascade}. In this context, the {\it Graph Inference} problem is the recovery of the graph's edges from the observation of few influence cascades. We propose to show how sparse recovery can be applied to solve this recently introduced graph inference problem.
 
-Recent research efforts in solving the graph inference problem have focused on constructing an effective algorithm which recovers a large majority of edges correctly from very few cascades. It has been shown that the graph inference problem can be solved in ${\cal O}(poly(s) \log m)$ number of observed cascades, where $s$ is the maximum degree and $m$ the number of nodes in the graph. In other words, the dependence of the number of cascades required to reconstruct the graph is (almost miraculously) logarithmic in the number of nodes of the graph. However, results in the sparse recovery literature lead us to believe that ${\cal O}(s \log m/s$ should be sufficient to recover the graph. In fact, we prove this lower bound in a very general sense. We also suggest a ${\cal O}(\Delta \log m)$-algorithm, which is almost tight. We also that the edge weights themselves can be estimated under the same assumptions.
+Tackling the graph inference problem means constructing a polynomial-time algorithm which recovers a large majority of edges correctly from very few observations or {\it cascades}. Prior work shown that the graph inference problem can be solved in ${\cal O}(poly(s) \log m)$ number of observed cascades, where $s$ is the maximum degree and $m$ is the number of nodes in the graph. Almost miraculously, the number of cascades required to reconstruct the graph is logarithmic in the number of nodes of the graph. Results in the sparse recovery literature lead us to believe that $\Omega(s \log m/s)$ cascade observations should be sufficient to recover the graph. In fact, we prove this lower bound in a very general sense. We show an almost tight upper-bound ${\cal O}(s \log m)$ by applying standard sparse recovery techniques and assumptions to the graph inference problem. We show that the edge weights themselves can also be recovered under the same assumptions.
 
-Since the first few papers on link prediction in networks, the research community has made good progress in defining the Graph Inference problem more clearly and suggesting effective algorithms. 
-
-Throughout this paper, we focus on the two main diffusion processes, outlined in the seminal work \cite{Kempe:03}: the independent cascade model (IC) and the linear threshold model.
+ Throughout this paper, we focus on the three main discrete-time diffusion processes: the independent cascade model, the voter model, and the linear threshold model...
 
 \subsection{Related Work}