From f6a02eeb1e006510bc2221eaac38681bc918c2c1 Mon Sep 17 00:00:00 2001
From: jeanpouget-abadie <jean.pougetabadie@gmail.com>
Date: Thu, 29 Jan 2015 11:09:29 -0500
Subject: updated assumptions section

---
 paper/sections/appendix.tex | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

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

diff --git a/paper/sections/appendix.tex b/paper/sections/appendix.tex
index 65576bb..eef3f45 100644
--- a/paper/sections/appendix.tex
+++ b/paper/sections/appendix.tex
@@ -1,6 +1,3 @@
-\subsection{Proof of support recovery lemma}
-
-
 \subsection{Upper-bound for $\|\nabla f(\theta^*)\|_\infty$}
 
 We show an upper-bound for $ 2 \|\nabla f(\theta^*) \|_\infty$. If we only consider the first measurement of every cascade, this can be done easily. Let $N$ be the number of cascades (to distinguish from $n$ number of total measurements). Begin by noting that for a node $\alpha$:
@@ -34,3 +31,14 @@ By union bound and characterization of sub-gaussian variables:
 \end{equation}
 
 In conclusion, for $\delta>0$, $\lambda := 2 \sqrt{\frac{n^{\delta + 1} \log m}{p_{\min}}}$ is a valid regularizer with probability $1 - \exp(-n^\delta \log m )$
+
+\subsection{Proposition~\ref{prop:irrepresentability}}
+In the words and notation of Theorem 9.1 in \cite{vandegeer:2009}: 
+\begin{lemma}
+\label{lemm:irrepresentability_proof}
+Let $\phi^2_{\text{compatible}}(L,S) \defeq \min \{ \frac{s \|f_\beta\|^2_2}{\|\beta_S\|^2_1} \ : \ \beta \in {\cal R}(L, S) \}$, where $\|f_\beta\|^2_2 \defeq \{ \beta^T \Sigma \beta \}$ and ${\cal R}(L,S) \defeq \{\beta : \|\beta_{S^c}\|_1 \leq L \|\beta_S\|_1 \neq 0\}$. If $\nu_{\text{irrepresentable}(S,s)} < 1/L$, then $\phi^2_{\text{compatible}}(L,S) \geq (1 - L \nu_{\text{irrepresentable}(S,s)})^2 \lambda_{\min}^2$. 
+\end{lemma}
+
+Since ${\cal R}(3, S) = {\cal C}$, $\|\beta_S\|_1 \geq \|\beta_S\|_2$, and $\|\beta_S\|_1 \geq \frac{1}{3} \|\beta_{S^c}\|_1$ it is easy to see that $\|\beta_S\|_1 \geq \frac{1}{4} \|\beta\|_2$ and therefore that: $\gamma_n \geq \frac{n}{4s}\phi^2_{\text{compatible}}(3,S)$
+
+Consequently, if $\epsilon > \frac{2}{3}$, then $\nu_{\text{irrepresentable}(S,s)} < 1/3$ and the conditions of Lemma~\ref{lemm:irrepresentability_proof} hold.
-- 
cgit v1.2.3-70-g09d2

