From c569d13f707706c49aea4cdd3635a0f73ed38f86 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Fri, 28 Jun 2013 18:04:04 +0200 Subject: Fixing notations in the proofs --- appendix.tex | 81 +++++++++++++----------------------------------------------- 1 file changed, 17 insertions(+), 64 deletions(-) (limited to 'appendix.tex') 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 -- cgit v1.2.3-70-g09d2