app:properties

1 files changed, 38 insertions, 28 deletions

diff --git a/appendix.tex b/appendix.tex
index f9564c3..9175e34 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -1,3 +1,30 @@
+\section{Properties of the Value Function $V$} \label{app:properties}
+For the sake of concreteness, we prove below the positivity, monotonicity, and submodularity of $V(S) = \log\det(I_d+X_S^TX_S)$ from basic principles. We note however that these properties hold more generally for the information gain under a wider class of models than the linear model with Gaussian noise and prior that we study here: we discuss this in more detail in Appendix~\ref{sec:ext}.
+
+For two symmetric matrices $A$ and $B$, we write $A\succ B$ ($A\succeq B$) if
+$A-B$ is positive definite (positive semi-definite).  This order allows us to
+define the notion of a \emph{decreasing} as well as  \emph{convex} matrix
+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
+    $S\subseteq \mathcal{N}$ can be written as 
+\begin{align}
+V(S\cup \{i\}) - V(S)& =   \frac{1}{2}\log\det(I_d 
+    + \T{X_S}X_S + x_i\T{x_i})
+    - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\nonumber\\
+    &  = \frac{1}{2}\log\det(I_d + x_i\T{x_i}(I_d +
+\T{X_S}X_S)^{-1})
+ = \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i)\label{eq:marginal_contrib}
+\end{align}
+where $A(S) \defeq I_d+ \T{X_S}X_S$, and the last equality follows from the
+Sylvester's determinant identity~\cite{sylvester}. Monotonicity therefore follows from the fact that $A(S)^{-1}$ is positive semidefinite. Finally, since the inverse is decreasing over positive definite matrices, we have
+\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
+
 
 \section{Proofs of Statements in Section~\ref{sec:concave}}
 \subsection{Proof of Lemma~\ref{lemma:relaxation-ratio}}\label{proofofrelaxation-ratio}
@@ -37,18 +64,9 @@
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\big(V(S\cup\{i\})
         - V(S)\big).
     \end{displaymath}
-    The marginal contribution of $i$ to
-    $S$ can be written as 
-\begin{align*}
-V(S\cup \{i\}) - V(S)& =   \frac{1}{2}\log\det(I_d 
-    + \T{X_S}X_S + x_i\T{x_i})
-    - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\\
-    &  = \frac{1}{2}\log\det(I_d + x_i\T{x_i}(I_d +
-\T{X_S}X_S)^{-1})
- = \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i)
-\end{align*}
-where $A(S) \defeq I_d+ \T{X_S}X_S$, and the last equality follows from the
-Sylvester's determinant identity~\cite{sylvester}.
+Recall from \eqref{eq:marginal_contrib} that the marginal contribution of $i$ to $S$ is given by
+$$V(S\cup \{i\}) - V(S) =\frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i), $$
+where $A(S) = I_d+ \T{X_S}X_S$.
 %  $  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}
@@ -58,7 +76,7 @@ Using this,
         \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
     \end{displaymath}
      The computation of the derivative of $L$ uses standard matrix
-    calculus: writing $\tilde{A}(\lambda) = I_d+\sum_{i\in
+    calculus: writing $\tilde{A}(\lambda) \defeq I_d+\sum_{i\in
     \mathcal{N}}\lambda_ix_i\T{x_i}$,
     \begin{displaymath}
         \det \tilde{A}(\lambda + h\cdot e_i) = \det\big(\tilde{A}(\lambda)
@@ -76,14 +94,7 @@ Using this,
         \partial_i L(\lambda)
         =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i.
     \end{displaymath}
-
-For two symmetric matrices $A$ and $B$, we write $A\succ B$ ($A\succeq B$) if
-$A-B$ is positive definite (positive semi-definite).  This order allows us to
-define the notion of a \emph{decreasing} as well as  \emph{convex} matrix
-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}).
-In particular,
+Recall from \eqref{eq:inverse} that the monotonicity of the matrix inverse over positive definite matrices implies 
 \begin{gather*}
         \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}
 \end{gather*}
@@ -96,8 +107,8 @@ for all $S\subseteq\mathcal{N}\setminus\{i\}$. Hence,
     & \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}
+    \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
+    +\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)\\
@@ -115,7 +126,7 @@ Hence,
     \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:
+positive definite matrices (see Appendix~\ref{app:properties}):
 \begin{displaymath}
     \partial_i F(\lambda) \geq
     \frac{1}{4}
@@ -126,7 +137,7 @@ positive definite matrices:
 \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.
+$F(\lambda)/L(\lambda)$ from below. Consider the following three 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:
@@ -643,7 +654,6 @@ The complexity of the mechanism is given by the following lemma.
 \end{proof}
 
 Finally, we prove the approximation ratio of the mechanism.
-
 We use the following lemma from \cite{chen} which bounds $OPT$ in terms of
 the value of $S_G$, as computed in Algorithm \ref{mechanism}, and $i^*$, the
 element of maximum value.
@@ -666,8 +676,8 @@ OPT
 \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!
 + \! \varepsilon .
 \end{equation}
-To see this, let $L^*_{c_{-i^*}}$ be the true maximum value of $L$ subject to
-$\lambda_{c_{-i^*}}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line
+To see this, let $L^*_{c_{-i^*}}$ be the  maximum value of $L$ subject to
+$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line
 \ref{relaxexec} of Algorithm~\ref{mechanism}, we have
 $L^*_{c_{-i^*}}-\varepsilon\leq OPT_{-i^*}' \leq L^*_{c_{-i^*}}+\varepsilon$.