From bca54732ef95d8a71437d76039b7b99b3e72ba29 Mon Sep 17 00:00:00 2001 From: jeanpouget-abadie Date: Sun, 7 Dec 2014 15:25:25 -0500 Subject: RIP constant section --- notes/cascades.png | Bin 73864 -> 0 bytes notes/icc.png | Bin 130144 -> 0 bytes notes/images/icc.png | Bin 0 -> 130144 bytes notes/images/voter.png | Bin 0 -> 111444 bytes notes/reportYaron.tex | 28 ++++++++++++++++++++++++++++ notes/voter.png | Bin 111444 -> 0 bytes 6 files changed, 28 insertions(+) delete mode 100644 notes/cascades.png delete mode 100644 notes/icc.png create mode 100644 notes/images/icc.png create mode 100644 notes/images/voter.png delete mode 100644 notes/voter.png (limited to 'notes') diff --git a/notes/cascades.png b/notes/cascades.png deleted file mode 100644 index 9f14d95..0000000 Binary files a/notes/cascades.png and /dev/null differ diff --git a/notes/icc.png b/notes/icc.png deleted file mode 100644 index 2148eed..0000000 Binary files a/notes/icc.png and /dev/null differ diff --git a/notes/images/icc.png b/notes/images/icc.png new file mode 100644 index 0000000..2148eed Binary files /dev/null and b/notes/images/icc.png differ diff --git a/notes/images/voter.png b/notes/images/voter.png new file mode 100644 index 0000000..c1325cb Binary files /dev/null and b/notes/images/voter.png differ diff --git a/notes/reportYaron.tex b/notes/reportYaron.tex index d39d060..6341f98 100644 --- a/notes/reportYaron.tex +++ b/notes/reportYaron.tex @@ -173,6 +173,34 @@ In general, the smaller $\delta_k$ is, the better we can recover $k$-sparse vect \subsection{Verifying the RIP constants} +Though it is not yet clear which normalization to choose for the columns of matrix $M$, nor whether we should include only the first step of every cascade or the cascade in its entirety, we ran simple experiments to show that the measurement matrix $M$ has `well-behaved' RIP constants. + +\begin{table} +\centering +\begin{tabular}{c | c | c | c } +c = 100 & c = 1000 & c = 100 & c = 1000 \\ +$p_\text{init}$ = .1 & $p_\text{init}$ = .1 & $p_\text{init}$ = .05 & $p_\text{init}$ = .05 \\ +\hline +$\delta_4 = .54$ & $\delta_4 = .37$ & $\delta_4 = .43$ & $\delta_4 = .23$ \\ +\end{tabular} +\caption{Results on dataset of 22 nodes extracted from the Karate club network. $p_\text{init}$ is the probability that a node is part of the seed set. $c$ is the number of cascades. $\delta_4$ is the RIP constant for $4$-sparse vectors. Cascades are generated using the independent cascade model.} +\end{table} + +Finding a non-trivial RIP constant is strongly NP-hard, and as such we were unable to test on networks with more than 25 nodes. To compute the $k-th$ RIP constant ($\delta_k$ with our notation), we must extract $k$ columns of $M$, and compute the following programs on the resulting matrices $(M_k)$ (there are $\binom{n}{k}$ of them!): +\begin{align} +\label{eq:lower_bound} +\min \qquad & \| M_k \vec x \|_2 \\ +\| \vec x\|_2 = 1 & \nonumber +\end{align} +\begin{align} +\label{eq:upper_bound} +\max \qquad & \| M_k \vec x \|_2 \\ +\| \vec x\|_2 = 1 & \nonumber +\end{align} + +Note how choosing the minimum of Eq~\ref{eq:lower_bound} over all extracted matrices returns the lowest possible $1 - \delta^-_k$ and choosing the maximum of Eq~\ref{eq:upper_bound} over all extracted matrices returns the highest possible $1 + \delta^+_k$. The smallest admissible $k-$RIP constant is therefore: $\max(\delta^+_k, \delta^-_k)$. Equations \ref{eq:lower_bound} and \ref{eq:upper_bound} can be solved efficiently since they correspond to the smallest and greatest eigenvalues of $M^TM$ respectively. + +In \cite{candes}, \subsection{Testing our algorithm} diff --git a/notes/voter.png b/notes/voter.png deleted file mode 100644 index c1325cb..0000000 Binary files a/notes/voter.png and /dev/null differ -- cgit v1.2.3-70-g09d2