Rewrite in terms of the regularization factor (\kappa/\sigma^2) which is denoted by \mu

1 files changed, 25 insertions, 22 deletions

diff --git a/proof.tex b/proof.tex
index af8bbb2..7b2088f 100644
--- a/proof.tex
+++ b/proof.tex
@@ -32,6 +32,7 @@
             \item $\varepsilon_i \sim \mathcal{N}(0,\sigma^2)$, 
                 $(\varepsilon_i)_{i\in \mathcal{N}}$ are mutually independent.
             \item prior knowledge of $\beta$: $\beta\sim\mathcal{N}(0,\kappa I_d)$
+            \item $\mu = \frac{\kappa}{\sigma^2}$ is the regularization factor.
         \end{itemize}
 \end{itemize}
 
@@ -42,7 +43,7 @@
         \begin{align*}
             \forall S\subset\mathcal{N},\; V(S)
             & = \frac{1}{2}\log\det\left(I_d
-                    + \frac{\kappa}{\sigma^2}\sum_{i\in S} x_ix_i^*\right)\\
+                    + \mu\sum_{i\in S} x_ix_i^*\right)\\
             & = \frac{1}{2}\log\det X(S)
         \end{align*}
     \item each user $i$ has a cost $c_i$
@@ -106,7 +107,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
                 P_\mathcal{N}(S,\lambda)X(S)\right)\\
                 & = \log\det \tilde{X}(\lambda)\\
             & = \log\det\left(I_d
-                + \frac{\kappa}{\sigma^2}\sum_{i\in\mathcal{N}}
+                + \mu\sum_{i\in\mathcal{N}}
                     \lambda_ix_ix_i^*\right)
         \end{align*}
 \end{itemize}
@@ -185,7 +186,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     The following inequality holds:
     \begin{displaymath}
         \forall\lambda\in[0,1]^n,\; 
-        \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{2\frac{\kappa}{\sigma^2}}
+        \frac{\log\big(1+\mu\big)}{2\mu}
         \,L_\mathcal{N}(\lambda)\leq
         F_\mathcal{N}(\lambda)\leq L_{\mathcal{N}}(\lambda)
     \end{displaymath}
@@ -195,7 +196,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
 
     We will prove that:
     \begin{displaymath}
-        \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{2\frac{\kappa}{\sigma^2}}
+        \frac{\log\big(1+\mu\big)}{2\mu}
     \end{displaymath}
     is a lower bound of the ratio $\partial_i F_\mathcal{N}(\lambda)/\partial_i
     L_\mathcal{N}(\lambda)$.
@@ -255,14 +256,14 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
         \partial_i F_\mathcal{N}(\lambda) = 
         \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_{\mathcal{N}\setminus\{i\}}(S,\lambda)
-        \log\Big(1 + \frac{\kappa}{\sigma^2}x_i^*X(S)^{-1}x_i\Big)
+        \log\Big(1 + \mu x_i^*X(S)^{-1}x_i\Big)
     \end{displaymath}
 
     The computation of the derivative of $L_\mathcal{N}$ uses standard matrix
     calculus and gives:
     \begin{displaymath}
         \partial_i L_\mathcal{N}(\lambda)
-        = \frac{\kappa}{\sigma^2}x_i^* \tilde{X}(\lambda)^{-1}x_i
+        = \mu x_i^* \tilde{X}(\lambda)^{-1}x_i
     \end{displaymath}
     
     Using the following inequalities:
@@ -277,36 +278,36 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
         \partial_i F_\mathcal{N}(\lambda) 
         & \geq \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_\mathcal{N}(S,\lambda)
-        \log\Big(1 + \frac{\kappa}{\sigma^2}x_i^*X(S)^{-1}x_i\Big)\\
+        \log\Big(1 + \mu x_i^*X(S)^{-1}x_i\Big)\\
         & \geq \frac{1}{2}
         \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_\mathcal{N}(S,\lambda)
-        \log\Big(1 + \frac{\kappa}{\sigma^2}x_i^*X(S)^{-1}x_i\Big)\\
+        \log\Big(1 + \mu x_i^*X(S)^{-1}x_i\Big)\\
         &\hspace{-3.5em}+\frac{1}{2}
         \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_\mathcal{N}(S\cup\{i\},\lambda)
-        \log\Big(1 + \frac{\kappa}{\sigma^2}x_i^*X(S\cup\{i\})^{-1}x_i\Big)\\
+        \log\Big(1 + \mu x_i^*X(S\cup\{i\})^{-1}x_i\Big)\\
         &\geq \frac{1}{2}
         \sum_{S\subset\mathcal{N}}
         P_\mathcal{N}(S,\lambda)
-        \log\Big(1 + \frac{\kappa}{\sigma^2}x_i^*X(S)^{-1}x_i\Big)\\
+        \log\Big(1 + \mu x_i^*X(S)^{-1}x_i\Big)\\
     \end{align*}
 
     Using that $X(S)\geq I_d$ we get that:
     \begin{displaymath}
-        \frac{\kappa}{\sigma^2}x_i^*X(S)^{-1}x_i \leq \frac{\kappa}{\sigma^2}
+        \mu x_i^*X(S)^{-1}x_i \leq \mu
     \end{displaymath}
     
     Moreover:
     \begin{displaymath}
-        \forall x\leq\frac{\kappa}{\sigma^2},\; \log(1+x)\geq
-    \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{\frac{\kappa}{\sigma^2}} x
+        \forall x\leq\mu,\; \log(1+x)\geq
+    \frac{\log\big(1+\mu\big)}{\mu} x
     \end{displaymath}
 
     Hence:
     \begin{displaymath}
         \partial_i F_\mathcal{N}(\lambda) \geq
-        \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{2\frac{\kappa}{\sigma^2}}
+        \frac{\log\big(1+\mu\big)}{2\mu}
         x_i^*\bigg(\sum_{S\subset\mathcal{N}}P_\mathcal{N}(S,\lambda)X(S)^{-1}\bigg)x_i
     \end{displaymath}
     
@@ -314,16 +315,18 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     positive definite matrices:
     \begin{align*}
         \partial_i F_\mathcal{N}(\lambda) &\geq
-        \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{2\frac{\kappa}{\sigma^2}}
+        \frac{\log\big(1+\mu\big)}{2\mu}
         x_i^*\bigg(\sum_{S\subset\mathcal{N}}P_\mathcal{N}(S,\lambda)X(S)\bigg)^{-1}x_i\\
-        & \geq \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{2\frac{\kappa}{\sigma^2}}
+        & \geq \frac{\log\big(1+\mu\big)}{2\mu}
         \partial_i L_\mathcal{N}(\lambda)
     \end{align*}
 \end{proof}
 
 \begin{lemma}
+    Let us denote by $C_\mu$ the constant of which appears in the bound of the
+    previous lemma: $C_\mu = \frac{\log(1+\mu)}{2\mu}$, then:
     \begin{displaymath}
-        OPT(L_\mathcal{N}, B) \leq \frac{1}{C_\kappa}\big(2 OPT(V,\mathcal{N},B)
+        OPT(L_\mathcal{N}, B) \leq \frac{1}{C_\mu}\big(2 OPT(V,\mathcal{N},B)
         + \max_{i\in\mathcal{N}}V(i)\big)
     \end{displaymath}
 \end{lemma}
@@ -334,7 +337,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     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 \frac{1}{C_\kappa}
+        L_\mathcal{N}(\lambda^*) \leq \frac{1}{C_\mu}
         F_\mathcal{N}(\bar{\lambda})
     \end{equation}
 
@@ -418,16 +421,16 @@ The mechanism is budget feasible.
 
     If the condition of the algorithm does not hold:
     \begin{align*}
-        V(i^*) & \leq \frac{1}{C}L(x^*) \leq \frac{1}{C\cdot C_\kappa}
+        V(i^*) & \leq \frac{1}{C}L(x^*) \leq \frac{1}{C\cdot C_\mu}
         \big(2 OPT(V,\mathcal{N}, B) + V(i^*)\big)\\
-        & \leq \frac{1}{C\cdot C_\kappa}\left(\frac{2e}{e-1}\big(3 V(S_M)
+        & \leq \frac{1}{C\cdot C_\mu}\left(\frac{2e}{e-1}\big(3 V(S_M)
         + 2 V(i^*)\big)
         + V(i^*)\right)
     \end{align*}
     
     Thus:
     \begin{align*}
-        V(i^*) \leq \frac{6e}{C\cdot C_\kappa(e-1)- 5e + 1} V(S_M)
+        V(i^*) \leq \frac{6e}{C\cdot C_\mu(e-1)- 5e + 1} V(S_M)
     \end{align*}
 
     Finally, using again that:
@@ -438,7 +441,7 @@ The mechanism is budget feasible.
     We get:
     \begin{displaymath}
         OPT(V, \mathcal{N}, B) \leq \frac{e}{e-1}\left( 3 + \frac{12e}{C\cdot
-        C_\kappa(e-1) -5e  +1}\right) V(S_M)
+        C_\mu(e-1) -5e  +1}\right) V(S_M)
     \end{displaymath}
 \end{proof}