diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 66 |
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$. |