From 33270e4737f4e76ac7e66f1044b615fa54737470 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 4 Nov 2012 18:27:20 -0800
Subject: co

---
 main.tex | 40 ++++++++++++++--------------------------
 1 file changed, 14 insertions(+), 26 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index b4c1861..0ce3598 100644
--- a/main.tex
+++ b/main.tex
@@ -503,7 +503,7 @@ For all $\lambda\in[0,1]^{n},$
   $  V(S\cup\{i\}) - V(S) = \frac{1}{2}\log\left(1 +  \T{x_i} A(S)^{-1}x_i\right)$.
 Using this,
     \begin{displaymath}
-        \partial_i F_\mathcal{N}(\lambda) = 
+        \partial_i F_\mathcal{N}(\lambda) = \frac{1}{2}
         \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)
         \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
@@ -512,7 +512,7 @@ Using this,
     calculus and gives:
     \begin{displaymath}
         \partial_i L_\mathcal{N}(\lambda)
-        = \T{x_i}\tilde{A}(\lambda)^{-1}x_i
+        =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i
     \end{displaymath}
     where $\tilde{A}(\lambda) = I_d+\sum_{i\in \mathcal{N}}\lambda_ix_i\T{x_i}$. Using the following inequalities (where $A\geq B$ implies $A-B$ is positive semi-definite):
     \begin{gather*}
@@ -526,18 +526,16 @@ Using this,
     we get:
     \begin{align*}
         \partial_i F_\mathcal{N}(\lambda) 
-        & = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_\mathcal{N}^\lambda(S)
-        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
-        & \geq \frac{1}{2}
+      %  & = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_\mathcal{N}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
+        & \geq \frac{1}{4}
         \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)
         \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
-        &\hspace{-3.5em}+\frac{1}{2}
+        &\hspace{-3.5em}+\frac{1}{4}
         \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})
         \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\
-        &\geq \frac{1}{2}
+        &\geq \frac{1}{4}
         \sum_{S\subseteq\mathcal{N}}
         P_\mathcal{N}^\lambda(S)
         \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
@@ -546,40 +544,34 @@ Using this,
     \begin{displaymath}
         \T{x_i}A(S)^{-1}x_i \leq \norm{x_i}_2^2 = 1 
     \end{displaymath}
-    
     Moreover:
     \begin{displaymath}
         \forall x\leq 1,\; \log(1+x)\geq x
     \end{displaymath}
-
     Hence:
     \begin{displaymath}
         \partial_i F_\mathcal{N}(\lambda) \geq
-        \frac{1}{2}
+        \frac{1}{4}
         \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)^{-1}\bigg)x_i
     \end{displaymath}
-    
     Finally, using that the inverse is a matrix convex function over symmetric
     positive definite matrices:
     \begin{align*}
         \partial_i F_\mathcal{N}(\lambda) &\geq
-        \frac{1}{2}
-        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i\\
-        & \geq \frac{1}{2}
+        \frac{1}{4}
+        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i
+         \geq \frac{1}{2}
         \partial_i L_\mathcal{N}(\lambda)\qed
     \end{align*}
 \end{proof}
-
-\begin{proof}
-    Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L_\mathcal{N}(\lambda^*)
-    = OPT(L_\mathcal{N}, B)$. By applying lemma~\ref{lemma:relaxation-ratio}
-    and lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most
+ To prove Lemma~\ref{lemma:relaxation},   let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L_\mathcal{N}(\lambda^*)
+    = OPT(L_\mathcal{N}, B)$. By applying Lemma~\ref{lemma:relaxation-ratio}
+    and Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most
     one fractional component such that:
     \begin{equation}\label{eq:e1}
         L_\mathcal{N}(\lambda^*) \leq 2
         F_\mathcal{N}(\bar{\lambda})
     \end{equation}
-
     Let $\lambda_i$ denote the fractional component of $\bar{\lambda}$ and $S$
     denote the set whose indicator vector is $\bar{\lambda} - \lambda_i e_i$.
     Using the fact that $F_\mathcal{N}$ is linear with respect to the $i$-th
@@ -587,20 +579,16 @@ Using this,
     \begin{displaymath}
         F_\mathcal{N}(\bar{\lambda}) = V(S) +\lambda_i V(S\cup\{i\})
     \end{displaymath}
-
     Using the submodularity of $V$:
     \begin{displaymath}
         F_\mathcal{N}(\bar{\lambda}) \leq 2 V(S) + V(i)
     \end{displaymath}
-
     Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and
     $V(S)\leq OPT(V,\mathcal{N}, B)$. Hence:
     \begin{equation}\label{eq:e2}
         F_\mathcal{N}(\bar{\lambda}) \leq 2 OPT(V,\mathcal{N}, B)
         + \max_{i\in\mathcal{N}} V(i)
     \end{equation}
-
-    Putting \eqref{eq:e1} and \eqref{eq:e2} together gives the results.
-\end{proof}
+    Together, \eqref{eq:e1} and \eqref{eq:e2} imply the lemma. \hspace*{\stretch{1}}\qed
 
 
-- 
cgit v1.2.3-70-g09d2

