\documentclass[11pt]{article}

\usepackage{amsmath, amssymb, amsthm}
\date{}
\author{}

\title{Supplementary Material \\ {\small Inferring Graphs from Cascades: A Sparse Recovery Framework}}

\begin{document}

\maketitle

\subsection*{(RE) with high probability}

\subsubsection*{(RE) for the gram matrix}

Recall the expression of the Hessian:
\begin{equation}
\nonumber
    \nabla^2\mathcal{L}(\theta^*)
    = \frac{1}{|\mathcal{T}|}\sum_{t\in\mathcal{T}}x^t(x^t)^T
    \bigg[x_i^{t+1}\frac{f''f-f'^2}{f^2}(\theta^* \cdot x^t)\\
    -(1-x_i^{t+1})\frac{f''(1-f) + f'^2}{(1-f)^2}(\theta^* \cdot x^t)\bigg]
\end{equation}

This can be rewritten as $X J X^T$ where $J$ is a diagonal matrix with coefficients either $g_1$ or $g_2$. Under certain regularity conditions for $f$ (such as strong log-concavity), we can consider only the gram matrix: $\Delta^T X^T J X \Delta \geq \gamma_1 \Delta^T X^T X \Delta$

Denote $p_i$ the probability that node $i$ is infected at the beginning of the cascade. Let $\mathbb{P}(i)$ be the probability that $i$ is infected at one point during a cascade. Let $\mathbb{P}(S)$ for any set $S \subseteq N$ be the probability that $S$ is infected (all at once) at one point during a cascade. The diagonal of the Gram Matrix can be written as:
\begin{equation}
\nonumber
c_j := \mathbb{P}(i) = p_i - \sum_{S \subseteq {\cal N}(i)} (-1)^{|S|} \mathbb{P}(S) \prod_{j \in S} w_{ji}  =  p_i + \sum_{j \in N(i)} w_{ji}c_j + \dots
\end{equation}
Note that we have the following bounds for $c_j$:

\begin{align}
c_j &\leq p_i + \sum_{j \in S} w_{ji} c_j \tag{PageRank}\\
c_j &\geq p_i + \max_{j \in S} w_{ji} c_j \tag{?}
\end{align}

\subsection*{Relaxed (RE) with high probability}

\subsection*{Lower Bound}

\end{document}