From 1bd9da9fc37dc4f659a261ff65914feef1ef64f0 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 2 Jul 2013 16:01:49 +0200
Subject: Rewrite the hand-wavy induction

---
 appendix.tex | 152 ++++++++++++++++++++++++++++++-----------------------------
 1 file changed, 78 insertions(+), 74 deletions(-)

(limited to 'appendix.tex')

diff --git a/appendix.tex b/appendix.tex
index b757e8e..ca6d1df 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -8,7 +8,7 @@ For all $\lambda\in[0,1]^{n},$
 \end{lemma}
 
 \begin{proof}
-    The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}(\lambda)}$ follows by the concavity of the $\log\det$ function.
+    The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}}(\lambda)$ follows by the concavity of the $\log\det$ function and Jensen's inequality.
     To show the lower bound, 
     we first prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i
     F(\lambda)/\partial_i L(\lambda)$, where
@@ -93,80 +93,84 @@ In particular,
 \begin{gather*}
         \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}
 \end{gather*}
-as $A(S)\preceq A(S\cup\{i\})$. Observe that
- %   \begin{gather*}
- %       \forall 
-$P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})$ for all $S\subseteq\mathcal{N}\setminus\{i\}$, and
-       % ,\\
-        $P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \geq P_\mathcal{N}^\lambda(S),$ for all $S\subseteq\mathcal{N}$.
- %\end{gather*}
-    Hence,
-    \begin{align*}
-        \partial_i F(\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}{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}{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}{4}
-        \sum_{S\subseteq\mathcal{N}}
-        P_\mathcal{N}^\lambda(S)
-        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big).
-    \end{align*}
-    Using that $A(S)\succeq I_d$ we get that $\T{x_i}A(S)^{-1}x_i \leq
-    \norm{x_i}_2^2 \leq 1$. Moreover, $\log(1+x)\geq x$ for all $x\leq 1$.
-    Hence,
-    \begin{displaymath}
-        \partial_i F(\lambda) \geq
-        \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{displaymath}
-        \partial_i F(\lambda) \geq
-        \frac{1}{4}
-        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i
-        = \frac{1}{4}\T{x_i}\tilde{A}(\lambda)^{-1}x_i
-         = \frac{1}{2}
-     \partial_i L(\lambda).
-    \end{displaymath}
+as $A(S)\preceq A(S\cup\{i\})$. Observe that since $1\leq \lambda_i\leq 1$, 
+$P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \geq P_\mathcal{N}^\lambda(S)$ and
+$P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq P_{\mathcal{N}}^\lambda(S\cup\{i\})$
+for all $S\subseteq\mathcal{N}\setminus\{i\}$. Hence,
+\begin{align*}
+    \partial_i F(\lambda) 
+    & \geq \frac{1}{4}
+    \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)\\
+    &\hspace{-3.5em}+\frac{1}{4}
+    \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+    P_{\mathcal{N}}^\lambda(S\cup\{i\})
+    \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\
+    &\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).
+\end{align*}
+Using that $A(S)\succeq I_d$ we get that $\T{x_i}A(S)^{-1}x_i \leq
+\norm{x_i}_2^2 \leq 1$. Moreover, $\log(1+x)\geq x$ for all $x\leq 1$.
+Hence,
+\begin{displaymath}
+    \partial_i F(\lambda) \geq
+    \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{displaymath}
+    \partial_i F(\lambda) \geq
+    \frac{1}{4}
+    \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i
+    = \frac{1}{4}\T{x_i}\tilde{A}(\lambda)^{-1}x_i
+    = \frac{1}{2}
+    \partial_i L(\lambda).
+\end{displaymath}
 
-Having bound the ratio between the partial derivatives, we now bound the ratio $F(\lambda)/L(\lambda)$ from below. Consider the following cases.
-    First, if the minimum of the ratio
-    $F(\lambda)/L(\lambda)$ is attained at a point interior to the hypercube, then it is
-    a critical point, \emph{i.e.}, $\partial_i \big(F(\lambda)/L(\lambda)\big)=0$ for all $i\in \mathcal{N}$; hence, at such a critical point:
-    \begin{equation}\label{eq:lhopital}
-        \frac{F(\lambda)}{L(\lambda)}
-        = \frac{\partial_i F(\lambda)}{\partial_i
-        L(\lambda)} \geq \frac{1}{2}.
-    \end{equation}
-    Second, if the minimum is attained as 
-    $\lambda$ converges to zero in, \emph{e.g.}, the $l_2$ norm, by the Taylor approximation, one can write:
-    \begin{displaymath}
-        \frac{F(\lambda)}{L(\lambda)}
-        \sim_{\lambda\rightarrow 0}
-        \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F(0)}
-        {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L(0)}
-        \geq \frac{1}{2},
-    \end{displaymath}
-    \emph{i.e.}, the ratio $\frac{F(\lambda)}{L(\lambda)}$ is necessarily bounded from below by 1/2 for small enough $\lambda$. 
-       Finally, if the minimum is attained on a face of the hypercube $[0,1]^n$ (a face is
-    defined as a subset of the hypercube where one of the variable is fixed to
-    0 or 1), without loss of generality, we can assume that the minimum is
-    attained on the face where the $n$-th variable has been fixed
-    to 0 or 1. Then, either the minimum is attained at a point interior to the
-    face or on a boundary of the face. In the first sub-case, relation
-    \eqref{eq:lhopital} still characterizes the minimum for $i< n$.
-    In the second sub-case, by repeating the argument again by induction, we see
-    that all is left to do is to show that the bound holds for the vertices of
-    the cube (the faces of dimension 1).  The vertices are exactly the binary
-    points, for which we know that both relaxations are equal to the value
-    function $V$. Hence, the ratio is equal to 1 on the vertices.
+Having bound the ratio between the partial derivatives, we now bound the ratio
+$F(\lambda)/L(\lambda)$ from below. Consider the following cases.
+
+First, if the minimum is attained as $\lambda$ converges to zero in,
+\emph{e.g.}, the $l_2$ norm, by the Taylor approximation, one can write:
+\begin{displaymath}
+    \frac{F(\lambda)}{L(\lambda)}
+    \sim_{\lambda\rightarrow 0}
+    \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F(0)}
+    {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L(0)}
+    \geq \frac{1}{2},
+\end{displaymath}
+\emph{i.e.}, the ratio $\frac{F(\lambda)}{L(\lambda)}$ is necessarily bounded
+from below by 1/2 for small enough $\lambda$.
+
+Second, if the minimum of the ratio $F(\lambda)/L(\lambda)$ is attained at
+a vertex of the hypercube $[0,1]^n$ different from 0. $F$ and $L$ being
+relaxations of the value function $V$, they are equal to $V$ on the vertices
+which are exactly the binary points. Hence the minimum is equal to 1 in this
+case. In particular it is greater than $1/2$.
+
+Finally, if the minimum is attained at a point $\lambda^*$ with at least one
+coordinate belonging to $(0,1)$, let $i$ be one such coordinate and consider
+the function $G_i$:
+\begin{displaymath}
+    G_i: x \mapsto \frac{F}{L}(\lambda_1^*,\ldots,\lambda_{i-1}^*, x,
+    \lambda_{i+1}^*, \ldots, \lambda_n^*).
+\end{displaymath}
+Then this function attains a minimum at $\lambda^*_i\in(0,1)$ and its
+derivative is zero at this point. Hence:
+\begin{displaymath}
+    0 = G_i'(\lambda^*_i) = \partial_i\left(\frac{F}{L}\right)(\lambda^*)
+\end{displaymath}.
+But $\partial_i(F/L)(\lambda^*)=0$ implies that
+\begin{displaymath}
+    \frac{F(\lambda^*)}{L(\lambda^*)} = \frac{\partial_i
+    F(\lambda^*)}{\partial_i L(\lambda^*)}\geq \frac{1}{2}
+\end{displaymath}
+using the lower bound on the ratio of the partial derivatives. This concludes
+the proof of the lemma.
 \end{proof}
 
 We now prove that $F$ admits the following exchange property: let
-- 
cgit v1.2.3-70-g09d2

