From a36c69aa005218ff7ebf6f7bb2ef3bd239b754f9 Mon Sep 17 00:00:00 2001
From: jeanpouget-abadie <jean.pougetabadie@gmail.com>
Date: Thu, 29 Jan 2015 09:50:23 -0500
Subject: small changes

---
 paper/sections/assumptions.tex | 32 ++++++++++++++++++++++++++------
 1 file changed, 26 insertions(+), 6 deletions(-)

(limited to 'paper/sections/assumptions.tex')

diff --git a/paper/sections/assumptions.tex b/paper/sections/assumptions.tex
index d6fed83..1f88494 100644
--- a/paper/sections/assumptions.tex
+++ b/paper/sections/assumptions.tex
@@ -1,13 +1,33 @@
-\subsection{The Restricted Eigenvalue Condition}
+\subsection{The Irrepresentability Condition}
 
-Proving the restricted eigenvalue assumption for correlated measurements is non-trivial. Under reasonable assumptions on the graph parameters, we can show a very crude ${\cal O}(N)$-lower bound for $\gamma_n$ by exploiting only the first set of measurements, where only the source nodes are active. Note that even though we waste a lot of information, we obtain similar asymptotic behavior than previous work.
+\cite{Daneshmand:2014} rely on an `incoherence' condition on the hessian of the likelihood function. It is in fact easy to see that their condition is equivalent to the more commonly called {\it (S, s)-irrepresentability} condition:
 
-\subsection{The Irrepresentability Condition}
+\begin{definition}
+Following similar notation, let $Q^* \nabla^2 f(\theta^*)$. Let $Q_{S^C,S} XXX$, the {\it (S, s)-irrepresentability} condition is defined as:
+\begin{equation}
+blabla
+\end{equation}
+\end{definition}
 
-If our objective is to recover only the support of the graph and to do it exactly , then the irrepresentability condition\footnote{{\it incoherence} in the text} used in \cite{Daneshmand:2014} is believed to be necessary. 
+If our objective is to recover the support of the graph exactly, the irrepresentability condition has been shown to be essentially necessary \cite{Zhao:2006}. However, several recent papers \cite{vandegeer:2011}, \cite{Zou:2006}, argue this condition is unrealistic in situations where there is a correlation between variables.
 
-However, assuming we only wish to recover all edges above a certain threshold, bounding the $\ell2$-error allows us to recover the full graph above a certain minimum threshold. Furthermore, it is intuitive that the irrepresentability condition is stronger than our suggested {\bf(RE)} assumption. In fact, by adapting slightly the following result from \cite{vandegeer:2009}, we can show that a `strong' irrepresentability condition directly {\it implies} the {\bf(RE)} condition for $\ell2$-recovery
+Consider for example the following matrix:
+
+Yet, assuming we only wish to recover all edges above a certain threshold, bounding the $\ell2$-error allows us to recover all edges with weights above a certain minimum threshold under an intuitively weaker {\bf(RE)} condition. In practical scenarios, such as in social networks, where one seeks to recover significant edges, this is a reasonable assumption.
+
+As mentioned previously, it is intuitive that the irrepresentability condition is stronger than our suggested {\bf(RE)} assumption. In fact, by adapting slightly the following result from \cite{vandegeer:2009}, we can show that a `strong' irrepresentability condition directly {\it implies} the {\bf(RE)} condition for $\ell2$-recovery
 
 \begin{proposition}
 If the irrepresentability condition holds with $\epsilon > \frac{2}{3}$, then the restricted eigenvalue condition holds with constant: $(1 - 3\epsilon)^2 \lambda_{\min}n/s$
-\end{proposition}
\ No newline at end of file
+\end{proposition}
+
+
+\subsection{The Restricted Eigenvalue Condition}
+
+Expressing the restricted eigenvalue assumption for correlated measurements is non-trivial as parameters of the graph is non-trivial. Under reasonable assumptions on the graph parameters, we can show a very crude ${\cal O}(N)$-lower bound for $\gamma_n$ by exploiting only the first set of measurements, where only the source nodes are active. Note that even though we waste a lot of information, we obtain similar asymptotic behavior than previous work.
+
+Similarly to the analysis conducted in \cite{Daneshmand:2014}, we can show that if the eigenvalue can be showed to hold for the `expected' hessian, it can be showed to hold for the hessian itself.
+
+\begin{proposition}
+If result holds for the expected hessian, then it holds for the hessian!
+\end{proposition}
-- 
cgit v1.2.3-70-g09d2

