diff options
| author | Thibaut Horel <thibaut.horel@gmail.com> | 2013-09-22 16:46:13 -0400 |
|---|---|---|
| committer | Thibaut Horel <thibaut.horel@gmail.com> | 2013-09-22 16:46:13 -0400 |
| commit | 0fb4e5a3e0beaf39e21273f4b0fdf7be92137f67 (patch) | |
| tree | a36ac257a78d81879928d4ff08a67ba7aeab949a /approximation.tex | |
| parent | d77abde7605a6fa3d9ddaca7dbfceb968a9dfbf0 (diff) | |
| parent | fc56a8f69d6eaeaecacdd4fdfa40df7e3d16599d (diff) | |
| download | recommendation-0fb4e5a3e0beaf39e21273f4b0fdf7be92137f67.tar.gz | |
Merge branch 'master' of ssh://74.95.195.229:1444/git/data_value
Diffstat (limited to 'approximation.tex')
| -rwxr-xr-x[-rw-r--r--] | approximation.tex | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/approximation.tex b/approximation.tex index cc278e1..1b94615 100644..100755 --- a/approximation.tex +++ b/approximation.tex @@ -47,7 +47,7 @@ expectation of $V$ under the distribution $P_\mathcal{N}^\lambda$: F(\lambda) \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big] % = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S) -= \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[ \log\det\left( I_d + \sum_{i\in S} x_i\T{x_i}\right) \right],\quad \lambda\in[0,1]^n. += \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[ \log\det\big( I_d + \textstyle\sum_{i\in S} x_i\T{x_i}\big) \big],\quad \lambda\in[0,1]^n. \end{equation} Function $F$ is an extension of $V$ to the domain $[0,1]^n$, as it equals $V$ on integer inputs: $F(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$. %\citeN{pipage} have shown how to use this extension to obtain approximation guarantees for an interesting class of optimization problems through the \emph{pipage rounding} framework, which has been successfully applied in \citeN{chen, singer-influence}. @@ -56,7 +56,7 @@ multi-linear extension \eqref{eq:multi-linear} cannot be optimized in polynomial time for the value function $V$ we study here, given by \eqref{modified}. Hence, we introduce an extension $L:[0,1]^n\to\reals$ s.t.~ \begin{equation}\label{eq:our-relaxation} L(\lambda) \defeq -\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right), +\log\det\big(I_d + \textstyle\sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\big), %= \log\det\left(\mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right), \quad \lambda\in[0,1]^n. \end{equation} |
