diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 10 |
1 files changed, 4 insertions, 6 deletions
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} |