diff options
Diffstat (limited to 'notes/reportYaron.tex')
| -rw-r--r-- | notes/reportYaron.tex | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/notes/reportYaron.tex b/notes/reportYaron.tex index 1dc0db1..78fe44c 100644 --- a/notes/reportYaron.tex +++ b/notes/reportYaron.tex @@ -246,6 +246,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} |