From 09e64e8bc5ff34ce9886e56cd918c2e03c45b283 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Mon, 18 May 2015 14:13:22 +0200 Subject: Pass on introduction. Add comment on correlated measurements --- paper/sections/intro.tex | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'paper') diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex index 7688aeb..4c18faf 100644 --- a/paper/sections/intro.tex +++ b/paper/sections/intro.tex @@ -65,11 +65,12 @@ A more recent line of research~\cite{Daneshmand:2014} has focused on applying advances in sparse 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~\cite{donoho2006compressed, candes2006near}. However, the -best known upper bound to this day is $\O(s^2\log m)$~\cite{Netrapalli:2012, -Daneshmand:2014} +lead to non-linear inverse problems and the measurements (the state of the +nodes at different time steps) are usually correlated. The sparse recovery +literature suggests that $\Omega(s\log\frac{m}{s})$ cascade observations should +be sufficient to recover the graph~\cite{donoho2006compressed, candes2006near}. +However, the best known upper bound to this day is $\O(s^2\log +m)$~\cite{Netrapalli:2012, Daneshmand:2014} The contributions of this paper are the following: -- cgit v1.2.3-70-g09d2