Fixing notations in the proofs

1 files changed, 17 insertions, 64 deletions

diff --git a/appendix.tex b/appendix.tex
index dd643d7..b757e8e 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -254,54 +254,6 @@ one fractional component such that
     \end{equation}
 Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qedhere
 
-\begin{proof}[Proof of Lemma~\ref{lemma:derivative-bounds}]
-    Let us define:
-    \begin{displaymath}
-        S(\lambda)\defeq I_d + \sum_{i=1}^n \lambda_i x_i\T{x_i}
-        \quad\mathrm{and}\quad
-        S_k \defeq I_d + \sum_{i=1}^k x_i\T{x_i}
-    \end{displaymath}
-
-    We have $\partial_i L(\lambda) = \T{x_i}S(\lambda)^{-1}x_i$. Since
-    $S(\lambda)\geq I_d$, $\partial_i L(\lambda)\leq \T{x_i}x_i \leq 1$, which
-    is the right-hand side  of the lemma.
-
-    For the left-hand side, note that $S(\lambda) \leq S_n$. Hence
-    $\partial_iL(\lambda)\geq \T{x_i}S_n^{-1}x_i$.
-
-    Using the Sherman-Morrison formula, for all $k\geq 1$:
-    \begin{displaymath}
-        \T{x_i}S_k^{-1} x_i = \T{x_i}S_{k-1}^{-1}x_i 
-        - \frac{(\T{x_i}S_{k-1}^{-1}x_k)^2}{1+\T{x_k}S_{k-1}^{-1}x_k}
-    \end{displaymath}
-
-    By the Cauchy-Schwarz inequality:
-    \begin{displaymath}
-        (\T{x_i}S_{k-1}^{-1}x_k)^2 \leq \T{x_i}S_{k-1}^{-1}x_i\;\T{x_k}S_{k-1}^{-1}x_k
-    \end{displaymath}
-
-    Hence:
-    \begin{displaymath}
-        \T{x_i}S_k^{-1} x_i \geq \T{x_i}S_{k-1}^{-1}x_i 
-        - \T{x_i}S_{k-1}^{-1}x_i\frac{\T{x_k}S_{k-1}^{-1}x_k}{1+\T{x_k}S_{k-1}^{-1}x_k}
-    \end{displaymath}
-
-    But $\T{x_k}S_{k-1}^{-1}x_k\leq 1$ and $\frac{a}{1+a}\leq \frac{1}{2}$ if
-    $0\leq a\leq 1$, so:
-    \begin{displaymath}
-        \T{x_i}S_{k}^{-1}x_i \geq \T{x_i}S_{k-1}^{-1}x_i
-        - \frac{1}{2}\T{x_i}S_{k-1}^{-1}x_i\geq \frac{\T{x_i}S_{k-1}^{-1}x_i}{2}
-    \end{displaymath}
-
-    By induction:
-    \begin{displaymath}
-        \T{x_i}S_n^{-1} x_i \geq \frac{\T{x_i}x_i}{2^n}
-    \end{displaymath}
-    
-    Using that $\T{x_i}{x_i}\geq b$ concludes the proof of the left-hand side
-    of the lemma's inequality.
-\end{proof}
-
 \subsection{Proof of Proposition~\ref{prop:monotonicity}}
 
 The $\log\det$ function is concave and self-concordant (see
@@ -328,47 +280,48 @@ Proposition~\ref{prop:monotonicity}.
 \end{lemma}
 
 \begin{proof}
-    Let us define:
+    Recall that we had defined:
     \begin{displaymath}
-        S(\lambda)\defeq I_d + \sum_{i=1}^n \lambda_i x_i\T{x_i}
+        \tilde{A}(\lambda)\defeq I_d + \sum_{i=1}^n \lambda_i x_i\T{x_i}
         \quad\mathrm{and}\quad
-        S_k \defeq I_d + \sum_{i=1}^k x_i\T{x_i}
+        A(S) \defeq I_d + \sum_{i\in S} x_i\T{x_i}
     \end{displaymath}
+    Let us also define $A_k\defeq A(\{x_1,\ldots,x_k\})$.
 
-    We have $\partial_i L(\lambda) = \T{x_i}S(\lambda)^{-1}x_i$. Since
-    $S(\lambda)\geq I_d$, $\partial_i L(\lambda)\leq \T{x_i}x_i \leq 1$, which
+    We have $\partial_i L(\lambda) = \T{x_i}\tilde{A}(\lambda)^{-1}x_i$. Since
+    $\tilde{A}(\lambda)\succeq I_d$, $\partial_i L(\lambda)\leq \T{x_i}x_i \leq 1$, which
     is the right-hand side  of the lemma.
 
-    For the left-hand side, note that $S(\lambda) \leq S_n$. Hence
-    $\partial_iL(\lambda)\geq \T{x_i}S_n^{-1}x_i$.
+    For the left-hand side, note that $\tilde{A}(\lambda) \preceq A_n$. Hence
+    $\partial_iL(\lambda)\geq \T{x_i}A_n^{-1}x_i$.
 
     Using the Sherman-Morrison formula, for all $k\geq 1$:
     \begin{displaymath}
-        \T{x_i}S_k^{-1} x_i = \T{x_i}S_{k-1}^{-1}x_i 
-        - \frac{(\T{x_i}S_{k-1}^{-1}x_k)^2}{1+\T{x_k}S_{k-1}^{-1}x_k}
+        \T{x_i}A_k^{-1} x_i = \T{x_i}A_{k-1}^{-1}x_i 
+        - \frac{(\T{x_i}A_{k-1}^{-1}x_k)^2}{1+\T{x_k}A_{k-1}^{-1}x_k}
     \end{displaymath}
 
     By the Cauchy-Schwarz inequality:
     \begin{displaymath}
-        (\T{x_i}S_{k-1}^{-1}x_k)^2 \leq \T{x_i}S_{k-1}^{-1}x_i\;\T{x_k}S_{k-1}^{-1}x_k
+        (\T{x_i}A_{k-1}^{-1}x_k)^2 \leq \T{x_i}A_{k-1}^{-1}x_i\;\T{x_k}A_{k-1}^{-1}x_k
     \end{displaymath}
 
     Hence:
     \begin{displaymath}
-        \T{x_i}S_k^{-1} x_i \geq \T{x_i}S_{k-1}^{-1}x_i 
-        - \T{x_i}S_{k-1}^{-1}x_i\frac{\T{x_k}S_{k-1}^{-1}x_k}{1+\T{x_k}S_{k-1}^{-1}x_k}
+        \T{x_i}A_k^{-1} x_i \geq \T{x_i}A_{k-1}^{-1}x_i 
+        - \T{x_i}A_{k-1}^{-1}x_i\frac{\T{x_k}A_{k-1}^{-1}x_k}{1+\T{x_k}A_{k-1}^{-1}x_k}
     \end{displaymath}
 
-    But $\T{x_k}S_{k-1}^{-1}x_k\leq 1$ and $\frac{a}{1+a}\leq \frac{1}{2}$ if
+    But $\T{x_k}A_{k-1}^{-1}x_k\leq 1$ and $\frac{a}{1+a}\leq \frac{1}{2}$ if
     $0\leq a\leq 1$, so:
     \begin{displaymath}
-        \T{x_i}S_{k}^{-1}x_i \geq \T{x_i}S_{k-1}^{-1}x_i
-        - \frac{1}{2}\T{x_i}S_{k-1}^{-1}x_i\geq \frac{\T{x_i}S_{k-1}^{-1}x_i}{2}
+        \T{x_i}A_{k}^{-1}x_i \geq \T{x_i}A_{k-1}^{-1}x_i
+        - \frac{1}{2}\T{x_i}A_{k-1}^{-1}x_i\geq \frac{\T{x_i}A_{k-1}^{-1}x_i}{2}
     \end{displaymath}
 
     By induction:
     \begin{displaymath}
-        \T{x_i}S_n^{-1} x_i \geq \frac{\T{x_i}x_i}{2^n}
+        \T{x_i}A_n^{-1} x_i \geq \frac{\T{x_i}x_i}{2^n}
     \end{displaymath}
     
     Using that $\T{x_i}{x_i}\geq b$ concludes the proof of the left-hand side