From 2d9b15a9ec01aa5cf90bf92edf24aab4fe6970c8 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Fri, 6 Feb 2015 16:53:13 -0500
Subject: Approximate sparsity

---
 paper/sections/results.tex | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

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

diff --git a/paper/sections/results.tex b/paper/sections/results.tex
index 5d63cbd..1688aae 100644
--- a/paper/sections/results.tex
+++ b/paper/sections/results.tex
@@ -241,18 +241,21 @@ which is also a consequence of Theorem 1 in \cite{Negahban:2009}.
 
 \begin{theorem}
 \label{thm:approx_sparse}
-Suppose the relaxed {\bf(RE)} assumption holds for the Hessian $\nabla^2
-f(\theta^*)$ and for the following set:
+Suppose the {\bf(RE)} assumption holds for the Hessian $\nabla^2
+f(\theta^*)$ and $\tau_{\mathcal{L}}(\theta^*) = \frac{\kappa_2\log m}{n}\|\theta^*\|_1$
+on the following set:
 \begin{align}
 \nonumber
-{\cal C}' \defeq & \{X \in \mathbb{R}^p : \|X_{S^c}\|_1 \leq 3 \|X_S\|_1 + 4 \|\theta^*_{\lfloor s \rfloor}\|_1 \} \\ \nonumber
+{\cal C}' \defeq & \{X \in \mathbb{R}^p : \|X_{S^c}\|_1 \leq 3 \|X_S\|_1
++ 4 \|\theta^* - \theta^*_{\lfloor s \rfloor}\|_1 \} \\ \nonumber
 & \cap \{ \|X\|_1 \leq 1 \}
 \end{align}
-By solving \eqref{eq:pre-mle} for $\lambda \defeq 2\sqrt{\frac{\log m}{\alpha n^{1 - \delta}}}$ we have:
+If the number of measurements $n\geq \frac{64\kappa_2}{\gamma}s\log m$, then
+by solving \eqref{eq:pre-mle} for $\lambda \defeq 2\sqrt{\frac{\log m}{\alpha n^{1 - \delta}}}$ we have:
 \begin{align*}
     \|\hat \theta - \theta^* \|_2 \leq
     \frac{3}{\gamma} \sqrt{\frac{s\log m}{\alpha n^{1-\delta}}}
-    + \frac{2}{\gamma} \sqrt[4]{\frac{s\log m}{\alpha n^{1-\delta}}} \|\theta^* - \theta^*_{\lfloor s \rfloor}\|_1
+    + 4 \sqrt[4]{\frac{s\log m}{\gamma^4\alpha n^{1-\delta}}} \|\theta^* - \theta^*_{\lfloor s \rfloor}\|_1
 \end{align*}
 \end{theorem}
 
-- 
cgit v1.2.3-70-g09d2

