diff options
| -rw-r--r-- | main.tex | 40 |
1 files changed, 14 insertions, 26 deletions
@@ -503,7 +503,7 @@ For all $\lambda\in[0,1]^{n},$ $ 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} - \partial_i F_\mathcal{N}(\lambda) = + \partial_i F_\mathcal{N}(\lambda) = \frac{1}{2} \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big) @@ -512,7 +512,7 @@ Using this, calculus and gives: \begin{displaymath} \partial_i L_\mathcal{N}(\lambda) - = \T{x_i}\tilde{A}(\lambda)^{-1}x_i + =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i \end{displaymath} where $\tilde{A}(\lambda) = I_d+\sum_{i\in \mathcal{N}}\lambda_ix_i\T{x_i}$. Using the following inequalities (where $A\geq B$ implies $A-B$ is positive semi-definite): \begin{gather*} @@ -526,18 +526,16 @@ Using this, we get: \begin{align*} \partial_i F_\mathcal{N}(\lambda) - & = \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)\\ - & \geq \frac{1}{2} + % & = \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)\\ + & \geq \frac{1}{4} \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\ - &\hspace{-3.5em}+\frac{1}{2} + &\hspace{-3.5em}+\frac{1}{4} \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\}) \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\ - &\geq \frac{1}{2} + &\geq \frac{1}{4} \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big) @@ -546,40 +544,34 @@ Using this, \begin{displaymath} \T{x_i}A(S)^{-1}x_i \leq \norm{x_i}_2^2 = 1 \end{displaymath} - Moreover: \begin{displaymath} \forall x\leq 1,\; \log(1+x)\geq x \end{displaymath} - Hence: \begin{displaymath} \partial_i F_\mathcal{N}(\lambda) \geq - \frac{1}{2} + \frac{1}{4} \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: \begin{align*} \partial_i F_\mathcal{N}(\lambda) &\geq - \frac{1}{2} - \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i\\ - & \geq \frac{1}{2} + \frac{1}{4} + \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i + \geq \frac{1}{2} \partial_i L_\mathcal{N}(\lambda)\qed \end{align*} \end{proof} - -\begin{proof} - Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L_\mathcal{N}(\lambda^*) - = OPT(L_\mathcal{N}, B)$. By applying lemma~\ref{lemma:relaxation-ratio} - and lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most + To prove Lemma~\ref{lemma:relaxation}, let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L_\mathcal{N}(\lambda^*) + = OPT(L_\mathcal{N}, B)$. By applying Lemma~\ref{lemma:relaxation-ratio} + and Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most one fractional component such that: \begin{equation}\label{eq:e1} L_\mathcal{N}(\lambda^*) \leq 2 F_\mathcal{N}(\bar{\lambda}) \end{equation} - Let $\lambda_i$ denote the fractional component of $\bar{\lambda}$ and $S$ denote the set whose indicator vector is $\bar{\lambda} - \lambda_i e_i$. Using the fact that $F_\mathcal{N}$ is linear with respect to the $i$-th @@ -587,20 +579,16 @@ Using this, \begin{displaymath} F_\mathcal{N}(\bar{\lambda}) = V(S) +\lambda_i V(S\cup\{i\}) \end{displaymath} - Using the submodularity of $V$: \begin{displaymath} F_\mathcal{N}(\bar{\lambda}) \leq 2 V(S) + V(i) \end{displaymath} - Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and $V(S)\leq OPT(V,\mathcal{N}, B)$. Hence: \begin{equation}\label{eq:e2} F_\mathcal{N}(\bar{\lambda}) \leq 2 OPT(V,\mathcal{N}, B) + \max_{i\in\mathcal{N}} V(i) \end{equation} - - Putting \eqref{eq:e1} and \eqref{eq:e2} together gives the results. -\end{proof} + Together, \eqref{eq:e1} and \eqref{eq:e2} imply the lemma. \hspace*{\stretch{1}}\qed |