diff options
Diffstat (limited to 'notes')
| -rw-r--r-- | notes/reportYaron.tex | 12 |
1 files changed, 8 insertions, 4 deletions
diff --git a/notes/reportYaron.tex b/notes/reportYaron.tex index feb5521..acdfaea 100644 --- a/notes/reportYaron.tex +++ b/notes/reportYaron.tex @@ -246,7 +246,9 @@ 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. +\paragraph{Motivation} 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. Indeed, the authors of \cite{candes} mention in their proofs that with an RIP strictly less than $\frac{1}{4}$, the assumptions of the theorem would hold, with slightly different constants. Due to a lack of time, we were unable to verify these claims or understand what the final statement of the theorem would be. In general, a measurement matrix with small RIP constants is known to recover sparse vectors well. These experiments should be considered as another reason to think that the sparse recovery framework is appropriate to the graph reconstruction problem. + +\paragraph{In practice} 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{table} \centering @@ -259,7 +261,7 @@ $\delta_4 = .54$ & $\delta_4 = .37$ & $\delta_4 = .43$ & $\delta_4 = .23$ \\ \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 \\ @@ -271,9 +273,11 @@ Finding a non-trivial RIP constant is strongly NP-hard, and as such we were unab \| \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. +\paragraph{Discussion} 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. + +The results of our findings on a very small social network (a subset of the famous Karate club), show that as the number of cascades increase the RIP constants decrease and that if $p_\text{init}$ is small then the RIP constant decrease as well. Finally the constants we obtain are either under or close to the $.25$ mark set by the authors of \cite{candes}. + -In \cite{candes}, \subsection{Testing our algorithm} |