Merge remote-tracking branch 'origin/master'

2 files changed, 157 insertions, 58 deletions

diff --git a/notes/cracking_cascades_classposter.tex b/notes/cracking_cascades_classposter.tex
index 52fd78d..9140e27 100644
--- a/notes/cracking_cascades_classposter.tex
+++ b/notes/cracking_cascades_classposter.tex
@@ -1,6 +1,6 @@
 \documentclass[final]{beamer}
 \usepackage[utf8]{inputenc}
-\usepackage[scale=1.41]{beamerposter} % Use the beamerposter package for laying out the poster
+\usepackage[scale=1.6]{beamerposter} % Use the beamerposter package for laying out the poster
 
 \usetheme{confposter} % Use the confposter theme supplied with this template
 
@@ -125,9 +125,8 @@
 \vspace{0.5 cm}
 
 \begin{itemize}
-\item Two types of nodes, {\color{red} red} and {\color{blue} blue}.
-\item $\mathbb{P}$(node is {\color{blue} blue} at $t=0) = p_{\text{init}}$
-\item $\mathbb{P}$(node is  {\color{blue} blue} at t+1) =  $\frac{\text{Number of {\color{blue}blue} neighbors}}{\text{Total number of neighbors}}$
+\item $\mathbb{P}$({\color{blue} blue} at $t=0) = p_{\text{init}}$
+\item $\mathbb{P}$({\color{blue} blue} at $t+1) =  \frac{\text{Number of {\color{blue}blue} neighbors}}{\text{Total number of neighbors}}$
 \end{itemize}
 
 \vspace{0.5 cm}
@@ -137,34 +136,40 @@
 \vspace{0.5 cm}
 
 
-To recover the neighbors of $v_1$:
-
-Observe which nodes are  {\color{red} red} (1) or {\color{blue} blue} (0) in the two first iterations:
+To recover the neighbors of $v_1$, observe which nodes are  {\color{red} red} (1) or {\color{blue} blue} (0) at time step $t$:
 \begin{align*}
-&v_2 \hspace{0.2 cm}  v_3 \hspace{0.2 cm} v_4 \hspace{0.2 cm} v_5 \\
+&v_2 \hspace{0.2 cm}  v_3 \hspace{0.2 cm} v_4 \hspace{0.2 cm} v_5 &\\
 \vspace{1 cm}
 M  = &  \left( \begin{array}{cccc}
 0 & 0 & 1 & 1 \\
 1 & 1 & 0 & 0 \\
-\end{array} \right) 
+\end{array} \right)  &  \begin{array}{l} \hspace{ - 5cm} 
+\text{time step 0} \\
+ \hspace{ - 5cm}  \text{time step 1} \\
+\end{array}
 \end{align*}
 
-and which color $v_1$ is in the two last iterations:
+and which color $v_1$ is at time step $t+1$ due to $M$:
 
 \begin{align*}
 b_1  = &  \left( \begin{array}{c}
 1 \\
 1 \\
-\end{array} \right) 
+\end{array} \right) &  \begin{array}{l} \hspace{ - 5cm} 
+\text{time step 1} \\
+ \hspace{ - 5cm}  \text{time step 2} \\
+ \end{array}
 \end{align*}
 
-If $(\vec x_{1})_j := \frac{\text{1}}{\text{deg}(i)} \cdot \left[\text{j parent of 1 in }{\cal G}\right] $, then our goal is to solve:
+Then ,
 
 \begin{equation}
 \boxed{M \vec x_1 = \vec b_1 + \epsilon \nonumber}
 \end{equation}
 
-This problem is a {\bf Noisy Sparse Recovery} problem, which has been studied extensively. Here, the vectors $\vec x_i$ are deg(i)-sparse. 
+where $(\vec x_{1})_j := \frac{\text{1}}{\text{deg}(i)} \cdot \left[\text{j parent of 1 in }{\cal G}\right] $
+
+
 \end{block}
 
 
@@ -203,47 +208,62 @@ This problem is a {\bf Noisy Sparse Recovery} problem, which has been studied ex
 \includegraphics[width=0.6\textwidth]{icc.png}
 \end{figure}
 
-{\bf Description}
+\vspace{0.5 cm}
 
+{\bf Description}
 
+\vspace{0.5 cm}
 
 \begin{itemize}
-\item Three possible states: susceptible  {\color{blue} blue}, infected  {\color{red} red}, inactive  {\color{yellow} yellow}
+\item Three possible states:   {\color{blue} susceptible},   {\color{red} infected},  {\color{yellow} inactive }
 \item $\mathbb{P}$(infected at t=0)$=p_{\text{init}}$
 \item Infected node $j$ infects its susceptible neighbors $i$ with probability $p_{j,i}$ independently
 \end{itemize}
 
+\vspace{0.5 cm}
 
 {\bf Sparse Recovery Formulation}
 
-To recover the neighbors of $v_5$:
+\vspace{0.5 cm}
 
-Observe which nodes are  {\color{red} red} (1), {\color{blue} blue} (0), or yellow {\color{yellow} yellow} (0) in the two first iterations:
+To recover the neighbors of $v_5$,observe which nodes are  {\color{red} red} (1), {\color{blue} blue} (0), or {\color{yellow} yellow} (0) at time step $t$:
 \begin{align*}
 &v_1 \hspace{0.2 cm}  v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \\
 \vspace{1 cm}
 M  = &  \left( \begin{array}{cccc}
 1 & 0 & 0 & 0 \\
 0 & 1 & 1 & 0 \\
-\end{array} \right) 
+\end{array} \right)   \begin{array}{l} \hspace{ 1cm} 
+\text{time step 0} \\
+ \hspace{ 1cm}  \text{time step 1} \\
+ \end{array}
 \end{align*}
 
-and if $v_5$ is infected in the two last iterations:
+and if $M$ caused $v_5$ to be infected at time step $t+1$:
 
 \begin{align*}
-b_1  = &  \left( \begin{array}{c}
+b_5  = &  \left( \begin{array}{c}
 0 \\
 1 \\
-\end{array} \right) 
+\end{array} \right)  \begin{array}{l} \hspace{ 1cm} 
+\text{time step 1} \\
+ \hspace{ 1cm}  \text{time step 2} \\
+ \end{array}
 \end{align*}
 
-If $(\vec \theta_i)_j := \log ( 1 - p_{j,i})  $, then our goal is to solve:
+
+Then,
 
 \begin{equation}
-\boxed{e^{M \vec \theta_i} = (1 - \vec b_i) + \epsilon} \nonumber
+\boxed{e^{M \vec \theta_5} = (1 - \vec b_5) + \epsilon} \nonumber
 \end{equation}
 
+where $(\vec \theta_5)_j := \log ( 1 - p_{j,5})  $
 
+\vspace{1 cm}
+
+
+This problem is a {\bf Noisy Sparse Recovery} problem, which has been studied extensively. Here, the vectors $\vec x_i$ are deg(i)-sparse. 
 
 
 \end{block}
@@ -252,27 +272,7 @@ If $(\vec \theta_i)_j := \log ( 1 - p_{j,i})  $, then our goal is to solve:
 
 
 
-\begin{block}{Algorithms}
 
-{\bf Voter Model}
-
-\begin{itemize}
-\item Solve for each node i:
-\begin{equation}
-\min_{\vec x_i} \|\vec x_i\|_1 + \lambda \|M \vec x_i - \vec b_i \|_2 \nonumber
-\end{equation}
-\end{itemize}
-
-{\bf Independent Cascade Model}
-
-\begin{itemize}
-\item Solve for each node i:
-\begin{equation}
-\min_{\vec \theta_i} \|\vec \theta_i\|_1 + \lambda \|e^{M \vec \theta_i} - \vec b_i \|_2 \nonumber
-\end{equation}
-\end{itemize}
-
-\end{block}
 
 
 
@@ -308,27 +308,42 @@ If $(\vec \theta_i)_j := \log ( 1 - p_{j,i})  $, then our goal is to solve:
 %----------------------------------------------------------------------------------------
 
 
+\begin{block}{Algorithms}
+
+{\bf Voter Model}
+
+\begin{itemize}
+\item Solve for each node i:
+\begin{equation}
+\min_{\vec x_i} \|\vec x_i\|_1 + \lambda \|M \vec x_i - \vec b_i \|_2 \nonumber
+\end{equation}
+\end{itemize}
+
+{\bf Independent Cascade Model}
+
+\begin{itemize}
+\item Solve for each node i:
+\begin{equation}
+\min_{\vec \theta_i} \|\vec \theta_i\|_1 + \lambda \|e^{M \vec \theta_i} - (1 - \vec b_i) \|_2 \nonumber
+\end{equation}
+\end{itemize}
 
+\end{block}
 
 \begin{block}{Restricted Isometry Property (RIP)}
 {\bf Definition}
 \begin{itemize}
-\item The Restricted Isometry Property (RIP) characterizes a quasi-orthonormality of the measurement matrix M on sparse vectors. 
+\item Characterizes a quasi-orthonormality of M on sparse vectors. 
 
-\item For all k, we define $\delta_k$ as the best possible constant such that for all unit-normed ($l$2) and k-sparse vectors $x$:
+\item The RIP constant $\delta_k$ is the best possible constant such that for all unit-normed ($l$2) and k-sparse vectors $x$:
 
 \begin{equation}
 1-\delta_k \leq \|Mx\|^2_2 \leq 1 + \delta_k \nonumber
 \end{equation}
 
-\item In general, the smaller $\delta_k$ is, the better we can recover $k$-sparse vectors $x$!
+\item The smaller $\delta_k$ is, the better we can recover $k$-sparse vectors $x$.
 \end{itemize}
 
-{\bf Relevance}
-\begin{itemize}
-\item Commonly studied in stable sparse recovery
-\item $\mathbb{E}_{a \in F}(a a^T) \approx I_n$ + RIP property (with $\delta = \frac{1}{4}$) should get similar conclusion as above
-\end{itemize}
 
 
 
@@ -336,13 +351,13 @@ If $(\vec \theta_i)_j := \log ( 1 - p_{j,i})  $, then our goal is to solve:
 
 \begin{block}{Theoretical Guarantees}
 
-In the case of small RIP constants $(\delta \leq 0.25)$ for $M$ and some assumption on the noise $\epsilon$:
+With small RIP constants $(\delta \leq 0.25)$ for $M$ and some assumption on the noise $\epsilon$:
 
 {\bf Theorem \cite{candes}}
 
 If node $i$ has degree $\Delta$  and $n_{\text{rows}}(M) \geq C_1 \mu \Delta \log n$, then, w.h.p.,
 
-$$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{m}}$$
+$$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{n_{\text{rows}}(M) }}$$
 
 
 \end{block}
@@ -354,14 +369,19 @@ $$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{m}}$
 %	RESULTS
 %----------------------------------------------------------------------------------------
 
-\begin{block}{Description of Experiments}
+\begin{block}{RIP Experiments}
 
-\begin{tabular}{ c | c | c | c | c }
-& c = 100, &c = 1000,&c = 100, &c = 1000,\\
-&  i = 0.1&i = 0.1& i = 0.05& i = 0.05\\
+\begin{center}
+\begin{table}
+\begin{tabular}{c | c | c | c | c }
+& $c$ = 100, &$c$ = 1000,& $c$ = 100, &$c$ = 1000,\\
+&  $i$ = 0.1& $i$ = 0.1& $i$ = 0.05& $i$ = 0.05\\
  \hline
   $\delta_4$ & 0.54 & 0.37 &0.43&0.23 \\
-\end{tabular}
+  \end{tabular} 
+  \caption{RIP constant for a small graph. Here, $c$ is the number of cascades and $i$ is $p_{\text{init}}$.}
+\end{table}
+\end{center}
 
 
 \end{block}
@@ -402,6 +422,12 @@ $$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{m}}$
 
 \begin{block}{Conclusion}
 
+\begin{center}
+
+
+{\bf Graph reconstruction can naturally be expressed as Sparse Recovery. Understanding properties of $M$, for example RIP, leads to theoretical guarantees on the reconstruction.}
+
+\end{center}
 
 \end{block}
 
diff --git a/notes/reportYaron.tex b/notes/reportYaron.tex
index 6341f98..78fe44c 100644
--- a/notes/reportYaron.tex
+++ b/notes/reportYaron.tex
@@ -84,6 +84,42 @@ If the vector $\vec x_i$ is sufficiently sparse, i.e. node $i$ has sufficiently
 
 \subsection{Example}
 
+
+\begin{figure}
+\centering
+\includegraphics[width=0.3\textwidth]{voter.png}
+\caption{A cascade in the voter model with time steps $t = 0,1,2$  over a graph with 5 vertices}
+\end{figure}
+
+
+
+
+To recover the neighbors of $v_1$, we get the following matrix $M$ for the example in Figure 1:
+
+\begin{align*}
+&\hspace{0.35cm} v_2 \hspace{0.2 cm}  v_3 \hspace{0.2 cm} v_4 \hspace{0.2 cm} v_5 &\\
+\vspace{1 cm}
+M  = &  \left( \begin{array}{cccc}
+0 & 0 & 1 & 1 \\
+1 & 1 & 0 & 0 \\
+\end{array} \right)  &  \begin{array}{l} \hspace{ -4.5 cm} 
+\text{time step 0} \\
+ \hspace{ - 4.5cm}  \text{time step 1} \\
+\end{array}
+\end{align*}
+
+and the vector $b_1$:
+
+\begin{align*}
+b_1  = &  \left( \begin{array}{c}
+1 \\
+1 \\
+\end{array} \right) &  \begin{array}{l} \hspace{ - 5cm} 
+\text{time step 1} \\
+ \hspace{ - 5cm}  \text{time step 2} \\
+ \end{array}
+\end{align*}
+
 \section{The Independent Cascade Model}
 
 \subsection{Description}
@@ -127,6 +163,43 @@ e^{M_i \vec \theta_i} = 1 - \vec b_i + \vec \epsilon_i
 
 Note that this is not exactly a sparse recovery model due to the non-linear exponential term. It is of the author's opinion however that if the probabilities $p_{j,i}$ are restrained to a bounded interval $[0, 1- \eta]$, then most of the results which hold for the linear voter model will continue to hold in this case.
 
+\subsection{Example}
+
+\begin{figure}
+\centering
+\includegraphics[width=0.3\textwidth]{icc.png}
+\caption{A cascade in the independent cascade model with time steps $t = 0,1,2$  over a graph with 5 vertices}
+\end{figure}
+
+
+
+To recover the neighbors of $v_5$, we get the following matrix $M$ for the example in Figure 2:
+\begin{align*}
+&v_1 \hspace{0.2 cm}  v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \\
+\vspace{1 cm}
+M  = &  \left( \begin{array}{cccc}
+1 & 0 & 0 & 0 \\
+0 & 1 & 1 & 0 \\
+\end{array} \right)   \begin{array}{l} \hspace{ 1cm} 
+\text{time step 0} \\
+ \hspace{ 1cm}  \text{time step 1} \\
+ \end{array}
+\end{align*}
+
+and the vector $b_5$:
+
+\begin{align*}
+b_5  = &  \left( \begin{array}{c}
+0 \\
+1 \\
+\end{array} \right)  \begin{array}{l} \hspace{ 1cm} 
+\text{time step 1} \\
+ \hspace{ 1cm}  \text{time step 2} \\
+ \end{array}
+\end{align*}
+
+
+
 \section{Sparse Recovery}
 
 \subsection{Introduction}