diff options
| -rw-r--r-- | jpa_test/cascade_creation.py | 3 | ||||
| -rw-r--r-- | jpa_test/make_plots.py | 12 | ||||
| -rw-r--r-- | jpa_test/rip_condition.py | 5 | ||||
| -rw-r--r-- | notes/beamerthemeconfposter.sty | 184 | ||||
| -rw-r--r-- | notes/cascades.png | bin | 0 -> 73864 bytes | |||
| -rw-r--r-- | notes/cracking_cascades_classposter.tex | 424 |
6 files changed, 620 insertions, 8 deletions
diff --git a/jpa_test/cascade_creation.py b/jpa_test/cascade_creation.py index a5c38cd..cc84c70 100644 --- a/jpa_test/cascade_creation.py +++ b/jpa_test/cascade_creation.py @@ -76,7 +76,8 @@ def icc_matrixvector_for_node(cascades, node): Returns M, w in matrix form where rows of M are i = t + k.T Excludes all (t,k) after node infection time; w = 1_{infected} """ - #TODO: you need to remove the variable corresponding to the node you are solving for!!!! + #TODO: you need to remove the variable corresponding to the node + #you are solving for!!!! if node is None: return np.vstack(cascades), None else: diff --git a/jpa_test/make_plots.py b/jpa_test/make_plots.py index ed7bb10..e3c0d3d 100644 --- a/jpa_test/make_plots.py +++ b/jpa_test/make_plots.py @@ -14,16 +14,18 @@ def plot_rip_numberofnodes(max_proba, n_min, n_max, p_init, n_cascades, K_max): for n_nodes in x: print n_nodes G = cascade_creation.InfluenceGraph(max_proba=.3) - G.erdos_init(n=n_nodes, p=.5) #TODO: handle different inits! + G.erdos_init(n=n_nodes, p=.1) #TODO: handle different inits! cascades = cascade_creation.generate_cascades(G, p_init=p_init, n_cascades=n_cascades) M, __ = cascade_creation.icc_matrixvector_for_node(cascades, None) M = cascade_creation.normalize_matrix(M) - y.append(rip_condition.find_kth_rip_constants(M, 5)) + y.append(rip_condition.find_kth_rip_constants(M, 4)) # + + print y plt.clf() plt.plot(x, y) - plt.show() + #plt.show() return x, y @@ -32,8 +34,8 @@ def test(): """ unit test """ - plot_rip_numberofnodes(max_proba=.3, n_min=10, n_max=15, - p_init=.3, n_cascades=10, K_max=5) + plot_rip_numberofnodes(max_proba=.3, n_min=30, n_max=30, + p_init=.01, n_cascades=100, K_max=4) if __name__=="__main__": test() diff --git a/jpa_test/rip_condition.py b/jpa_test/rip_condition.py index 7c1ce85..fccf9a4 100644 --- a/jpa_test/rip_condition.py +++ b/jpa_test/rip_condition.py @@ -10,11 +10,12 @@ def find_kth_rip_constants(M, k): 1 + A_1 = arg max |Mx|_2^2 s.t. |x|_2 = 1 and |x|_0 = k 1 - A_2 = arg min |Mx|_2^2 s.t. |x|_2 = 1 and |x|_0 = kx """ - delta = 10 + delta = 0 + print M.shape for col_set in itertools.combinations(xrange(M.shape[1]), k): M_kcol = M[:,list(col_set)] delta_upper, delta_lower = upperlower_bound_rip(M_kcol) - delta = min(delta, min(delta_upper, delta_lower)) + delta = max(delta, max(delta_upper, delta_lower)) return delta diff --git a/notes/beamerthemeconfposter.sty b/notes/beamerthemeconfposter.sty new file mode 100644 index 0000000..bcba6a7 --- /dev/null +++ b/notes/beamerthemeconfposter.sty @@ -0,0 +1,184 @@ +%============================================================================== +% Beamer style for the poster template posted at +% www.nathanieljohnston.com/index.php/2009/08/latex-poster-template +% +% Created by the Computational Physics and Biophysics Group at Jacobs University +% https://teamwork.jacobs-university.de:8443/confluence/display/CoPandBiG/LaTeX+Poster +% Modified by Nathaniel Johnston (nathaniel@nathanieljohnston.com) in August 2009 +% ============================================================================= + +\ProvidesPackage{beamerthemeconfposter} +\RequirePackage{tikz} % for drawing the nice rounded boxes +\usetikzlibrary{arrows,backgrounds} +\RequirePackage[T1]{fontenc} +\RequirePackage{lmodern} +\RequirePackage{textcomp} +\RequirePackage{amsmath,amssymb} +\usefonttheme{professionalfonts} +\newcommand{\makeruleinbox}{{\usebeamercolor[bg]{block alerted title}\centering\hspace*{-0.7cm}\rule{\inboxrule}{0.5cm}}} +\usepackage{ragged2e} +\usepackage{wrapfig} +%----------------------------------------------------------- +% Define a whole bunch of custom colours and fonts +%----------------------------------------------------------- + +\definecolor{lgreen} {RGB}{180,210,100} +\definecolor{dblue} {RGB}{20,66,129} +\definecolor{ddblue} {RGB}{11,36,69} +\definecolor{lred} {RGB}{220,0,0} +\definecolor{nred} {RGB}{224,0,0} +\definecolor{norange}{RGB}{244,127,36} +\definecolor{nyellow}{RGB}{255,221,0} +\definecolor{ngreen} {RGB}{98,158,31} +\definecolor{dgreen} {RGB}{78,138,21} +\definecolor{nblue} {RGB}{28,130,185} +\definecolor{jblue} {RGB}{20,50,100} +\definecolor{jalpha} {RGB}{0,0,0} + +% set the basic colors +\setbeamercolor{palette primary} {fg=black,bg=white} +\setbeamercolor{palette secondary} {fg=black,bg=white} +\setbeamercolor{palette tertiary} {bg=jblue,fg=white} +\setbeamercolor{palette quaternary}{fg=black,bg=white} +\setbeamercolor{structure}{fg=jblue} +\setbeamercolor{titlelike} {bg=jblue,fg=white} +\setbeamercolor{frametitle} {bg=jblue!10,fg=jblue} +\setbeamercolor{cboxb}{fg=black,bg=jblue} +\setbeamercolor{cboxr}{fg=black,bg=red} + +% set colors for itemize/enumerate +\setbeamercolor{item}{fg=ngreen} +\setbeamercolor{item projected}{fg=white,bg=ngreen} + +% set colors for blocks +%\setbeamercolor{block title}{fg=ngreen,bg=white} +%\setbeamercolor{block body}{fg=black,bg=white} + +%set colors for alerted blocks (blocks with frame) +\setbeamercolor{block alerted title}{fg=white,bg=jblue} +\setbeamercolor{block alerted body}{fg=black,bg=jblue!10} + +% set the fonts +\setbeamerfont{section in head/foot}{series=\bfseries} +\setbeamerfont{block title}{series=\bfseries} +\setbeamerfont{block alerted title}{series=\bfseries} +\setbeamerfont{frametitle}{series=\bfseries} +\setbeamerfont{frametitle}{size=\Large} + +% set some beamer theme options +\setbeamertemplate{title page}[default][colsep=-4bp,rounded=true] +\setbeamertemplate{sections/subsections in toc}[square] +\setbeamertemplate{items}[circle] +\setbeamertemplate{blocks}[width=0.0] +\beamertemplatenavigationsymbolsempty + +% set bibliography style +\setbeamertemplate{bibliography item}[text] +\setbeamercolor{bibliography item}{fg=black,bg=white} +\setbeamercolor{bibliography entry author}{fg=black,bg=white} +\setbeamercolor{bibliography item}{fg=black,bg=white} + +% define some length variables that are used by the template +\newlength{\inboxwd} +\newlength{\iinboxwd} +\newlength{\inboxrule} +\makeatletter +\makeatother + +%============================================================================== +% build the poster title +%============================================================================== +\setbeamertemplate{headline}{ + \leavevmode + \begin{columns} + \begin{column}{.2\linewidth} + \vskip1cm + \centering + %\includegraphics[height=4in]{UIUC-logo} + \end{column} + \vspace{1cm} + \begin{column}{.6\linewidth} + \vskip1cm + \centering + \usebeamercolor{title in headline}{\color{jblue}\Huge{\textbf{\inserttitle}}\\[0.5ex]} + \usebeamercolor{author in headline}{\color{fg}\Large{\insertauthor}\\[1ex]} + \usebeamercolor{institute in headline}{\color{fg}\large{\insertinstitute}\\[1ex]} + \vskip1cm + \end{column} + \vspace{1cm} + \begin{column}{.2\linewidth} + \vskip1cm + \centering + %\includegraphics[height=4in]{graph500-logo} + \vskip1cm + \end{column} + \vspace{1cm} + \end{columns} + \vspace{0.5in} + \hspace{0.5in}\begin{beamercolorbox}[wd=47in,colsep=0.15cm]{cboxb}\end{beamercolorbox} + \vspace{0.1in} +} + +% Block definition +\setbeamertemplate{block begin} +{ + \par\vskip\medskipamount + \begin{beamercolorbox}[colsep*=0ex,dp={2ex},center]{block title} + \vskip-0.25cm + \usebeamerfont{block title}\large\insertblocktitle + \begin{flushleft} + \vskip-1cm + \begin{tikzpicture}[remember picture,overlay] + \shade [inner color=gray,outer color=white] + (0,0) rectangle (\textwidth,0.3cm); + \end{tikzpicture} + \end{flushleft} + \end{beamercolorbox} + {\parskip0pt\par} + \ifbeamercolorempty[bg]{block title} + {} + {\ifbeamercolorempty[bg]{block body}{}{\nointerlineskip\vskip-0.5pt}} + \usebeamerfont{block body} + \vskip-0.5cm + \begin{beamercolorbox}[colsep*=0ex,vmode]{block body} + \justifying +} + +\setbeamertemplate{block end} +{ + \end{beamercolorbox} + \vskip\smallskipamount +} + +% Alert block definition (with frame) +\setbeamertemplate{block alerted begin} +{ + \par\vskip\medskipamount + \begin{beamercolorbox}[sep=0ex,rounded=true,center,dp={2ex}]{block alerted title} + \vskip0.01cm + \usebeamerfont{block title}\large\insertblocktitle + \end{beamercolorbox} + {\parskip0pt\par} + \usebeamerfont{block body} + \vskip-0.8cm + \begin{beamercolorbox}[sep=0.5cm, rounded=true,center]{block alerted title} + \setlength{\inboxwd}{\linewidth} + \addtolength{\inboxwd}{-1cm} + \begin{beamercolorbox}[rounded=true,wd={\inboxwd},center]{block alerted body} + \setlength{\iinboxwd}{\inboxwd} + \setlength{\inboxrule}{\inboxwd} + \addtolength{\iinboxwd}{-0.5cm} + \addtolength{\inboxrule}{0.5cm} + \begin{center} + \begin{minipage}{\iinboxwd} + \justifying +} + +\setbeamertemplate{block alerted end} +{ + \end{minipage} + \end{center} + \end{beamercolorbox} + \end{beamercolorbox} + \vskip\smallskipamount +}
\ No newline at end of file diff --git a/notes/cascades.png b/notes/cascades.png Binary files differnew file mode 100644 index 0000000..9f14d95 --- /dev/null +++ b/notes/cascades.png diff --git a/notes/cracking_cascades_classposter.tex b/notes/cracking_cascades_classposter.tex new file mode 100644 index 0000000..2b29109 --- /dev/null +++ b/notes/cracking_cascades_classposter.tex @@ -0,0 +1,424 @@ +\documentclass[final]{beamer} +\usepackage[utf8]{inputenc} +\usepackage[scale=1.41]{beamerposter} % Use the beamerposter package for laying out the poster + +\usetheme{confposter} % Use the confposter theme supplied with this template + +\usepackage{color, bbm} +\setbeamercolor{block title}{fg=dblue,bg=white} % Colors of the block titles +\setbeamercolor{block body}{fg=black,bg=white} % Colors of the body of blocks +\setbeamercolor{block alerted title}{fg=white,bg=dblue!70} % Colors of the highlighted block titles +\setbeamercolor{block alerted body}{fg=black,bg=dblue!10} % Colors of the body of highlighted blocks +% Many more colors are available for use in beamerthemeconfposter.sty + +%----------------------------------------------------------- +% Define the column widths and overall poster size +% To set effective sepwid, onecolwid and twocolwid values, first choose how many columns you want and how much separation you want between columns +% In this template, the separation width chosen is 0.024 of the paper width and a 4-column layout +% onecolwid should therefore be (1-(# of columns+1)*sepwid)/# of columns e.g. (1-(4+1)*0.024)/4 = 0.22 +% Set twocolwid to be (2*onecolwid)+sepwid = 0.464 +% Set threecolwid to be (3*onecolwid)+2*sepwid = 0.708 + +\newlength{\sepwid} +\newlength{\onecolwid} +\newlength{\twocolwid} +\newlength{\threecolwid} +\setlength{\paperwidth}{48in} % A0 width: 46.8in +\setlength{\paperheight}{40in} % A0 height: 33.1in +\setlength{\sepwid}{0.024\paperwidth} % Separation width (white space) between columns +\setlength{\onecolwid}{0.22\paperwidth} % Width of one column +\setlength{\twocolwid}{0.464\paperwidth} % Width of two columns +\setlength{\threecolwid}{0.708\paperwidth} % Width of three columns +\setlength{\topmargin}{-1in} % Reduce the top margin size +%----------------------------------------------------------- + +\usepackage{graphicx} % Required for including images + +\usepackage{booktabs} % Top and bottom rules for tables + + + +%---------------------------------------------------------------------------------------- +% TITLE SECTION +%---------------------------------------------------------------------------------------- + +\title{Sparse Recovery for Graph Reconstruction } % Poster title + +\author{Eric Balkanski, Jean Pouget-Abadie} % Author(s) + +\institute{Harvard University} % Institution(s) +%---------------------------------------------------------------------------------------- +\begin{document} +\addtobeamertemplate{block end}{}{\vspace*{2ex}} % White space under blocks +\addtobeamertemplate{block alerted end}{}{\vspace*{2ex}} % White space under highlighted (alert) blocks + +\setlength{\belowcaptionskip}{2ex} % White space under figures +\setlength\belowdisplayshortskip{2ex} % White space under equations + +\begin{frame}[t] % The whole poster is enclosed in one beamer frame + +\begin{columns}[t] % The whole poster consists of three major columns, the second of which is split into two columns twice - the [t] option aligns each column's content to the top + +\begin{column}{\sepwid}\end{column} % Empty spacer column + +\begin{column}{\onecolwid} % The first column + +%---------------------------------------------------------------------------------------- +% INTODUCTION +%---------------------------------------------------------------------------------------- + + +%\vspace{- 15.2 cm} +%\begin{center} +%{\includegraphics[height=7em]{logo.png}} % First university/lab logo on the left +%\end{center} + +%\vspace{4.6 cm} + +\begin{block}{Introduction} + +{\bf Graph Reconstruction}: + +\begin{itemize} +\item \{${\cal G}, \vec p$\}: directed graph, edge probabilities +\item $F$: cascade generating model +\item ${\cal M} := F\{{\cal G}, \vec p\}$: cascade +\end{itemize} + +{\bf Objective}: +\begin{itemize} +\item Find algorithm which computes $F^{-1}({\cal M}) = \{{\cal G}, \vec p\}$ w.h.p., i.e. recovers graph from cascades. +\end{itemize} + +{\bf Approach} +\begin{itemize} +\item Frame graph reconstruction as a {\it Sparse Recovery} problem for two cascade generating models. +\end{itemize} + +%Given a set of observed cascades, the \textbf{graph reconstruction problem} consists of finding the underlying graph on which these cascades spread. We assume that these cascades come from the classical \textbf{Independent Cascade Model} where at each time step, newly infected nodes infect each of their neighbor with some probability. + +%In previous work, this problem has been formulated in different ways, including a convex optimization and a maximum likelihood problem. However, there is no known algorithm for graph reconstruction with theoretical guarantees and with a reasonable required sample size. + +%We formulate a novel approach to this problem in which we use \textbf{Sparse Recovery} to find the edges in the unknown underlying network. Sparse Recovery is the problem of finding the sparsest vector $x$ such that $\mathbf{M x =b}$. In our case, for each node $i$, we wish to recover the vector $x = p_i$ where $p_{i_j}$ is the probability that node $j$ infects node $i$ if $j$ is active. To recover this vector, we are given $M$, where row $M_{t,k}$ indicates which nodes are infected at time $t$ in observed cascade $k$, and $b$, where $b_{t+1,k}$ indicates if node $i$ is infected at time $t+1$ in cascade $k$. Since most nodes have a small number of neighbors in large networks, we can assume that these vectors are sparse. Sparse Recovery is a well studied problem which can be solved efficiently and with small error if $M$ satisfies certain properties. In this project, we empirically study to what extent $M$ satisfies the Restricted Isometry Property. + +\end{block} + +%--------------------------------------------------------------------------------- +%--------------------------------------------------------------------------------- + +\begin{block}{Voter Model} +{\bf Description} + +\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 Observe until horizon T +\end{itemize} + +{\bf Sparse Recovery Formulation} +\begin{itemize} +\item Definitions: +\end{itemize} +\begin{align} +(\vec m^t_k)_j &:= \left[\text{node j is {\color{blue} blue} at t in cascade k}\right] \nonumber \\ +(\vec x_{i})_j &:= \frac{\text{1}}{\text{deg}(i)} \cdot \left[\text{j parent of i in }{\cal G}\right] \nonumber \\ +b^t_{k,i} &:= \text{node i is {\color{blue} blue} at t+1 in cascade k} \nonumber +\end{align} + +\begin{itemize} +\item Observation: +\end{itemize} +\begin{align} +\langle \vec m^t_k, \vec x_i \rangle &= \mathbb{P}(\text{node i is {\color{blue} blue} at t+1 in cascade k}) \nonumber \\ +&=: w^{t+1}_{k,i} \nonumber +\end{align} + +\begin{itemize} +\item We observe $M := \text{vstack}(\vec m^t_k)$ +\item We observe $b_i := \text{vstack}(b^t_{k,i})$ where $$b^t_{k,i} \sim {\cal B}(w^t_{k,i}) = w^t_{k,i} - \epsilon$$ +\item For each node i, solve for $\vec x_i$: +\begin{equation} +\boxed{M \vec x_i = \vec b_i + \epsilon \nonumber} +\end{equation} +\end{itemize} +\end{block} + + + + + +%--------------------------------------------------------------------------------- +%--------------------------------------------------------------------------------- + + +%--------------------------------------------------------------------------------- +%--------------------------------------------------------------------------------- + +\begin{block}{Independent Cascade Model} + +{\bf Description} +\begin{itemize} +\item Three possible states: susceptible, infected, inactive +\item Infected node $j$ infects its susceptible neighbors $i$ with probability $p_{j,i}$ independently +\item $\mathbb{P}$(inactive at t+1| infected at t) = 1 +\item $\mathbb{P}$(infected at t=0)$=p_{\text{init}}$ +\end{itemize} + + +{\bf Sparse Recovery Formulation} +\begin{itemize} + +\item Definitions: +\begin{align} +(\vec \theta_i)_j &:= \log ( 1 - p_{j,i}) \nonumber \\ +(\vec m^t_k)_j &= \left[\text{node j is infected at t in cascade k}\right] \nonumber +\end{align} + +\item Observation: +\begin{equation} +\langle \vec m^t_k, \vec x_i \rangle = \log \mathbb{P}(\text{node i {\it not} infect. at t+1 in casc. k}) \nonumber +\end{equation} +\item With same notations, we solve for each node i: +\begin{equation} +\boxed{e^{M \vec \theta_i} = (1 - \vec b_i) + \epsilon} \nonumber +\end{equation} +where: $e^{M \vec \theta_i}$ is taken element-wise +\end{itemize} +\end{block} + + + + + +%--------------------------------------------------------------------------------- +%--------------------------------------------------------------------------------- + + + +\end{column} % End of the first column + +\begin{column}{\sepwid}\end{column} % Empty spacer column + +\begin{column}{\onecolwid} % The first column + +%---------------------------------------------------------------------------------------- +% CONSTRAINT SATISFACTION - BACKTRACKING +%---------------------------------------------------------------------------------------- +\begin{block}{Example} + +\begin{figure} +\centering +\includegraphics[width=0.6\textwidth]{cascades.png} +\caption{Two cascades with two time steps each. Red nodes are the infected and active nodes.} +\end{figure} + +Figure 1 illustrates two cascades. In this case, if we wish to recover $p_A$, then our problem would be is given by the formula +\[ \left( \begin{array}{cccc} +1 & 0 & 0 & 0 \\ +0 & 1 & 0 & 0 \\ +\end{array} \right) x_A = \left( \begin{array}{c} +0 \\ +1 \\\end{array} \right)\] + +\end{block} + +%---------------------------------------------------------------------------------------- + +\begin{block}{Motivation} +\begin{itemize} +\item Vectors $\vec x_i$ are deg(i)-sparse. +\item Matrix $M$ is well-conditioned (see experimental section) +\item Voter model: quasi-textbook noisy sparse recovery +\item Independent cascade: if $p_{j,i} < 1 - \eta$, exponential can be approximated by affine function +\end{itemize} +\end{block} + +\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} +where: $e^{M \vec \theta_i}$ is taken element-wise +\end{itemize} + +\end{block} + + + + + +%---------------------------------------------------------------------------------------- +% MIP +%---------------------------------------------------------------------------------------- + +% \begin{block}{RIP property} + +% %The Restricted Isometry Property (RIP) characterizes a quasi-orthonormality of the measurement matrix M on sparse vectors. + +% 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$ + +% \begin{equation} +% 1-\delta_k \leq \|Mx\|^2_2 \leq 1 + \delta_k +% \end{equation} + +% In general, the smaller $\delta_k$ is, the better we can recover $k$-sparse vectors $x$! + +% \end{block} + +%---------------------------------------------------------------------------------------- + +\end{column} + +\begin{column}{\sepwid}\end{column} % Empty spacer column + +\begin{column}{\onecolwid} % The first column within column 2 (column 2.1) + + +%---------------------------------------------------------------------------------------- + + +\begin{block}{Theoretical Guarantees} + +{\bf Assumptions} +\begin{itemize} +\item Suppose that each row of $M$ is taken from a distribution $F$, such that +\begin{itemize} + \item $\mathbb{E}_{a \in F}(a a^T) = I_n$ + \item $\|a\|_{\infty} \leq \mu$ +\end{itemize} +\item Suppose that w.h.p $\| M^T \epsilon \|_{\infty} \leq 2.5 \sqrt{\log n} $ +\end{itemize} + +{\bf Theorem \cite{candes}} + +If node $i$ has degree $\Delta$ and $n_{\text{rows}}(M) \geq C \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}}$$ + +{\bf Discussion} + +\begin{itemize} +\item If we consider $M/p_{init}$, then $\mathbb{E}_{a \in F}(a a^T) \approx I_n$ +\item $\mathbb{E}(\epsilon) = 0$, hence $\| M^T \epsilon \|_{\infty} \leq 2.5 \sqrt{\log n}$ should hold w.h.p +\end{itemize} + +\end{block} + + +\begin{block}{Restriced 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 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$: + +\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$! +\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} + + + +\end{block} + + + +%---------------------------------------------------------------------------------------- +% RESULTS +%---------------------------------------------------------------------------------------- + +\begin{block}{Description of Experiments} + + + +\end{block} + +%---------------------------------------------------------------------------------------- + + +\end{column} % End of the second column + +\begin{column}{\sepwid}\end{column} % Empty spacer column + +\begin{column}{\onecolwid} % The third column + +%---------------------------------------------------------------------------------------- +% IOVERALL COMPARISON +%---------------------------------------------------------------------------------------- + +%\vspace{- 14.2 cm} +%\begin{center} +%{\includegraphics[height=7em]{cmu_logo.png}} % First university/lab logo on the left +%\end{center} + +%\vspace{4 cm} + +\begin{alertblock}{Experimental Results} + + + + +\end{alertblock} + +%---------------------------------------------------------------------------------------- + + +%---------------------------------------------------------------------------------------- +% CONCLUSION +%---------------------------------------------------------------------------------------- + +\begin{block}{Conclusion} + + +\end{block} + +%---------------------------------------------------------------------------------------- +% REFERENCES +%---------------------------------------------------------------------------------------- + +\begin{block}{References} + +\begin{thebibliography}{42} + +\bibitem{candes} +Candès, E., and Plan, Y. +\newblock {\it A Probabilistic and RIPless Theory of Compressed Sensing} +\newblock Information Theory, IEEE Transactions on, 57(11): 7235--7254, +\newblock 2011. +\end{thebibliography} + +\end{block} + +%---------------------------------------------------------------------------------------- + +\end{column} % End of the third column + +\end{columns} % End of all the columns in the poster + +\end{frame} % End of the enclosing frame + + + +\end{document} |
