From c8725444de7c890cf3c8c394b671553e6677faf4 Mon Sep 17 00:00:00 2001
From: jeanpouget-abadie <jean.pougetabadie@gmail.com>
Date: Sun, 1 Feb 2015 20:26:16 -0500
Subject: assumptions

---
 paper/sections/assumptions.tex | 20 +++-----------------
 1 file changed, 3 insertions(+), 17 deletions(-)

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

diff --git a/paper/sections/assumptions.tex b/paper/sections/assumptions.tex
index 7cf9345..896011c 100644
--- a/paper/sections/assumptions.tex
+++ b/paper/sections/assumptions.tex
@@ -2,23 +2,9 @@ In this section, we discuss the main assumption of Theorem~\ref{thm:neghaban} na
 
 \subsection{The Restricted Eigenvalue Condition}
 
-The restricted eigenvalue condition, introduced in \cite{bickel:2009}, is one of the weakest sufficient condition on the design matrix for successful sparse recovery \cite{vandegeer:2009}. Several recent papers show that large classes of correlated designs obey the restricted eigenvalue property with high probability \cite{raskutti:10} \cite{rudelson:13}. Expressing the minimum restricted eigenvalue $\gamma$ as a function of the cascade model parameters is highly non-trivial. However, the restricted eigenvalue property is however well behaved in the following sense:
-
-\begin{lemma}
-\label{lem:expected_hessian}
-Expected hessian analysis!
-\end{lemma}
-
-This result is easily proved by adapting slightly a result from \cite{vandegeer:2009} XXX. 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. It is easy to see that:
-
-\begin{proposition}
-\label{prop:expected_hessian}
-If result holds for the expected hessian, then it holds for the hessian!
-\end{proposition}
-
-It is most likely possible to remove this extra s factor. See sub-gaussian paper by ... but the calculations are more involved.
-
+The restricted eigenvalue condition, introduced in \cite{bickel:2009}, is one of the weakest sufficient condition on the design matrix for successful sparse recovery \cite{vandegeer:2009}. Several recent papers show that large classes of correlated designs obey the restricted eigenvalue property with high probability \cite{raskutti:10} \cite{rudelson:13}. Expressing the minimum restricted eigenvalue $\gamma$ as a function of the cascade model parameters is highly non-trivial. However, the restricted eigenvalue property is however well behaved in the following sense: under reasonable assumptions, if the population matrix of the hessian $\mathbb{E} \left[\nabla^2 {\cal L}(\theta) \right]$, corresponding to the \emph{Fisher Information Matrix} of the Cascade Model as a function of $\Theta$, verifies the restricted eigenvalue property, then the finite sample hessian also verifies the restricted eigenvalue property with overwhelming probability. It is straightforward to show this holds when $n \geq \Omega s^2 \log m$ \cite{vandegeer:2009}. By adapting Theorem 8 \cite{rudelson:13}\footnote{this result still needs to be confirmed!}, this can be reduced to:
 
+$$n \geq C s \log m \log^3 \left( \frac{s \log m}{C'} \right)$$
 
 \subsection{The Irrepresentability Condition}
 
@@ -44,7 +30,7 @@ I_s & \rho J \\
 \end{equation}
 where $I_s$ is the $s \times s$ identity matrix, $J$ is the all-ones matrix and $\rho \in \mathbb{R}^+$. It is easy to see that $\nu_{\text{irrepresentable}}(S) = \rho s$ and $\lambda_{\min}(Q) \geq 1 - \rho$, such that for any $\rho > \frac{1}{s}$ and $\rho < 1$, the restricted eigenvalue holds trivially but the (S,s)-irrepresentability does not hold.
 
-It is intuitive that the irrepresentability condition is stronger than the {\bf(RE)} assumption. In fact, a slightly modified result from \cite{vandegeer:2009}shows that a `strong' irrepresentability condition directly {\it implies} the {\bf(RE)} condition for $\ell2$-recovery:
+It is intuitive that the irrepresentability condition is stronger than the {\bf(RE)} assumption. In fact, a slightly modified result from \cite{vandegeer:2009} shows that a `strong' irrepresentability condition directly {\it implies} the {\bf(RE)} condition for $\ell2$-recovery:
 
 \begin{proposition}
 \label{prop:irrepresentability}
-- 
cgit v1.2.3-70-g09d2

