From b1afe9b3e8d876f4ddb7e8364c115ea41379457f Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 7 Jul 2013 22:13:12 -0700
Subject: minor edits

---
 appendix.tex | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

(limited to 'appendix.tex')

diff --git a/appendix.tex b/appendix.tex
index 6be1a85..904bd45 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -8,7 +8,7 @@ function, similarly to their real counterparts. With this definition, matrix
 inversion is decreasing and convex over symmetric positive definite
 matrices (see Example 3.48 p. 110 in \cite{boyd2004convex}).
 
-The positivity of $V(S)$ follows from the fact that $X_S^TX_S$ is positive semi-definite and, as such $I_d+X_S^TX_S\succeq I_d$, so all its eigenvalues are larger or equal to one, and they are all one if and only if $S=\emptyset$. The marginal contribution of item $i\in\mathcal{N}$ to set
+Recall that the determinant of a matrix equals the product of its eigenvalues. The positivity of $V(S)$ follows from the fact that $X_S^TX_S$ is positive semi-definite and, as such $I_d+X_S^TX_S\succeq I_d$, so all its eigenvalues are larger than or equal to one, and they are all one if $S=\emptyset$. The marginal contribution of item $i\in\mathcal{N}$ to set
     $S\subseteq \mathcal{N}$ can be written as 
 \begin{align}
 V(S\cup \{i\}) - V(S)& =   \frac{1}{2}\log\det(I_d 
@@ -23,13 +23,13 @@ Sylvester's determinant identity~\cite{sylvester}. Monotonicity therefore follow
 \begin{gather}
         \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}. \label{eq:inverse}
 \end{gather}
-and submodularity also follows. \qed
+and submodularity also follows, as a function is submodular if and only if the marginal contributions are non-increasing in $S$. \qed
 
 
 \section{Proofs of Statements in Section~\ref{sec:concave}}
 \subsection{Proof of Lemma~\ref{lemma:relaxation-ratio}}\label{proofofrelaxation-ratio}
 %\begin{proof}
-    The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}}(\lambda)$ follows by the concavity of the $\log\det$ function and Jensen's inequality.
+    The bound $F(\lambda)\leq L(\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 we use
@@ -411,17 +411,15 @@ In particular, $|L^*_c - L^*_{c,\alpha}| \leq \alpha n^2$.
         = \frac{1}{\max_{i\in\bar{M}} c_i}
     \end{equation}
     where the last inequality uses Lemma~\ref{lemma:derivative-bounds}.
-
     Combining \eqref{local-2}, \eqref{local-3} and \eqref{local-4}, we get that:
     \begin{displaymath}
         \sum_{i\in M}\mu_i^* \leq |M|\xi^*B \leq n\xi^*B\leq \frac{nB}{\max_{i\in\bar{M}} c_i} \leq n^2
     \end{displaymath}
-    
     This implies that:
     \begin{displaymath}
         \T{\mathbf{1}}\mu^* = \sum_{i=1}^n \mu^*_i = \sum_{i\in M}\mu_i^*\leq n^2
     \end{displaymath}
-    which in addition to \eqref{eq:local-1} proves the lemma.
+    which along with \eqref{eq:local-1} proves the lemma.
 \end{proof} 
 
 \begin{lemma}\label{lemma:monotonicity}
-- 
cgit v1.2.3-70-g09d2

