Small fixes to sections 4 and 5

3 files changed, 87 insertions, 67 deletions

diff --git a/main.tex b/main.tex
index 7e9fe02..9891fb3 100644
--- a/main.tex
+++ b/main.tex
@@ -151,9 +151,9 @@ We can now state our main result:
         \varepsilon\\
         & \simeq 12.98V(S^*) + \varepsilon
     \end{align*}
-    The value of the constant $C$ is given by \eqref{eq:constant} in
-    Section~\ref{sec:proofofmainthm}.
 \end{theorem}
+The value of the constant $C$ is given by \eqref{eq:constant} in
+Section~\ref{sec:proofofmainthm}.
 
 \fussy
 In addition, we prove the following simple lower bound.
diff --git a/notes.bib b/notes.bib
index ef54082..5225644 100644
--- a/notes.bib
+++ b/notes.bib
@@ -619,3 +619,27 @@ year = "2011"
   bibsource = {DBLP, http://dblp.uni-trier.de}
 }
 
+@article{sylvester,

+title = "Various proofs of Sylvester's (determinant) identity",

+journal = "Mathematics and Computers in Simulation",

+volume = "42",

+number = "4–6",

+pages = "585 - 593",

+year = "1996",

+note = "<ce:title>Sybolic Computation, New Trends and Developments</ce:title>",

+issn = "0378-4754",

+doi = "10.1016/S0378-4754(96)00035-3",

+url = "http://www.sciencedirect.com/science/article/pii/S0378475496000353",

+author = "Alkiviadis G. Akritas and Evgenia K. Akritas and Genadii I. Malaschonok",

+keywords = "Sylvester's identity",

+keywords = "Polynomial remainder sequence (prs)",

+keywords = "Matrix-triangularization subresultant prs"

+}

+
+@techreport{convexmatrix,
+  title={Matrix convex functions with applications to weighted centers for semidefinite programming},
+  author={Brinkhuis, J. and Luo, Z.Q. and Zhang, S.},
+  year={2005},
+  institution={Erasmus School of Economics (ESE)}
+}
+
diff --git a/proofs.tex b/proofs.tex
index eb1226c..2cff729 100644
--- a/proofs.tex
+++ b/proofs.tex
@@ -36,7 +36,7 @@ following lemma  which establishes that $OPT'$, the optimal value \eqref{relax}
  is not too far from $OPT$.  
 \begin{lemma}[Approximation]\label{lemma:relaxation}
      $   OPT' \leq 2 OPT
-        + 2\max_{i\in\mathcal{N}}V(i)$
+        + 2\max_{i\in\mathcal{N}}V(i)$.
 \end{lemma}
 The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}.
 
@@ -48,7 +48,7 @@ $S^*$ allocated by the mechanism is such that:
 \begin{equation} \label{approxbound}
 OPT
 \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!
-+ \! \varepsilon 
++ \! \varepsilon .
 \end{equation}
 To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to
 $\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume
@@ -57,53 +57,52 @@ $\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq \tilde{L}+\varepsilon$ has been
 computed (Lemma~\ref{lemma:complexity} states that this  is computed in time
 within our complexity guarantee).
 
-If the condition on line 3 of the algorithm holds, then:
+If the condition on line 3 of the algorithm holds, then
 \begin{displaymath}
     V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq
-    \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C} 
+    \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}
 \end{displaymath}
 as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$,
-hence:
+hence,
 \begin{equation}\label{eq:bound1}
-    OPT\leq (1+C)V(i^*) + \varepsilon
+    OPT\leq (1+C)V(i^*) + \varepsilon.
 \end{equation}
 
 If the condition  does not hold, by observing that $OPT'_{-i^*}\leq OPT'$ and
-applying Lemma~\ref{lemma:relaxation}, we get:
+applying Lemma~\ref{lemma:relaxation}, we get
 \begin{displaymath}
     V(i^*)  \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C}
-    \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}
+    \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}.
 \end{displaymath}
-Applying Lemma~\ref{lemma:greedy-bound}:
+Applying Lemma~\ref{lemma:greedy-bound},
 \begin{displaymath}
     V(i^*) \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G)
-    + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C}
+    + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C}.
 \end{displaymath}
 Thus, if $C$ is such that $C(e-1) -6e  +2 > 0$,
 \begin{align*}
     V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) 
-    + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}
+    + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}.
 \end{align*}
-Finally, using Lemma~\ref{lemma:greedy-bound} again, we get:
+Finally, using Lemma~\ref{lemma:greedy-bound} again, we get
 \begin{equation}\label{eq:bound2}
     OPT(V, \mathcal{N}, B) \leq 
     \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}\right) V(S_G)
-    + \frac{2e\varepsilon}{C(e-1)- 6e + 2}
+    + \frac{2e\varepsilon}{C(e-1)- 6e + 2}.
 \end{equation}
 To minimize the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1}
-and \eqref{eq:bound2} respectively, we wish to chose for $C=C^*$ such that:
+and \eqref{eq:bound2} respectively, we wish to chose $C$ that minimizes
 \begin{displaymath}
-    C^* = \argmin_C 
     \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}
-            \right)\right)
+            \right)\right).
 \end{displaymath}
-This equation has two solutions. Only one of those is such that $C(e-1) -6e
-+2 \geq 0$. This solution is:
+This function has two minima, only one of those is such that $C(e-1) -6e
++2 \geq 0$. This minimum is
 \begin{equation}\label{eq:constant}
-    C^* =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}
+    C =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}.
 \end{equation}
-For this solution, $\frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon.$
-Placing the expression of $C^*$ in \eqref{eq:bound1} and \eqref{eq:bound2}
+For this minimum, $\frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon.$
+Placing the expression of $C$ in \eqref{eq:bound1} and \eqref{eq:bound2}
 gives the approximation ratio in \eqref{approxbound}, and concludes the proof
 of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed
 
@@ -241,22 +240,23 @@ For all $\lambda\in[0,1]^{n},$
 
    Let us start by computing the derivatives of $F$ and
     $L$ with respect to the $i$-th component.
-    Observe that:
+    Observe that
     \begin{displaymath}
         \partial_i P_\mathcal{N}^\lambda(S) = \left\{
             \begin{aligned}
-                & P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})\;\textrm{if}\; i\in S \\
+                & P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})\;\textrm{if}\;
+                i\in S, \\
                 & - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\;\textrm{if}\;
-                i\in \mathcal{N}\setminus S \\
+                i\in \mathcal{N}\setminus S. \\
             \end{aligned}\right.
     \end{displaymath}
-    Hence:
+    Hence,
     \begin{displaymath}
         \partial_i F(\lambda) =
         \sum_{\substack{S\subseteq\mathcal{N}\\ i\in S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})V(S)
         - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)
+        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S).
     \end{displaymath}
     Now, using that every $S$ such that $i\in S$ can be uniquely written as
     $S'\cup\{i\}$, we can write:
@@ -264,7 +264,7 @@ For all $\lambda\in[0,1]^{n},$
         \partial_i F(\lambda) =
         \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\big(V(S\cup\{i\})
-        - V(S)\big)
+        - V(S)\big).
     \end{displaymath}
     The marginal contribution of $i$ to
     $S$ can be written as 
@@ -276,7 +276,8 @@ V(S\cup \{i\}) - V(S)& =   \frac{1}{2}\log\det(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) =I_d+ \T{X_S}X_S$. 
+where $A(S) \defeq I_d+ \T{X_S}X_S$, and the last equality follows from the
+Sylvester's determinant identity~\cite{sylvester}.
 %  $  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}
@@ -286,43 +287,44 @@ 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
-    \mathcal{N}}\lambda_ix_i\T{x_i}$:
+    calculus: writing $\tilde{A}(\lambda) = 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)
         + hx_i\T{x_i}\big)
          =\det \tilde{A}(\lambda)\big(1+
-        h\T{x_i}\tilde{A}(\lambda)^{-1}x_i\big)
+        h\T{x_i}\tilde{A}(\lambda)^{-1}x_i\big).
     \end{displaymath}
-    Hence:
+    Hence,
     \begin{displaymath}
        \log\det\tilde{A}(\lambda + h\cdot e_i)= \log\det\tilde{A}(\lambda)
-        + h\T{x_i}\tilde{A}(\lambda)^{-1}x_i + o(h)
+        + h\T{x_i}\tilde{A}(\lambda)^{-1}x_i + o(h),
     \end{displaymath}
-    Finally:
+    which implies
     \begin{displaymath}
         \partial_i L(\lambda)
-        =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i
+        =\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.
+inversion is decreasing and convex over symmetric positive definite
+matrices~\cite{convexmatrix}.
 In particular,
 \begin{gather*}
         \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}
 \end{gather*}
- Observe that:
+as $A(S)\leq A(S\cup\{i\})$. Observe that
     \begin{gather*}
         \forall S\subseteq\mathcal{N}\setminus\{i\},\quad
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})\\
+        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\}),\\
         \forall S\subseteq\mathcal{N},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S) 
-        \geq P_\mathcal{N}^\lambda(S)
+        \geq P_\mathcal{N}^\lambda(S).
     \end{gather*}
-    Hence:
+    Hence,
     \begin{align*}
         \partial_i F(\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)\\
@@ -337,15 +339,15 @@ In particular,
         &\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)
+        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big).
     \end{align*}
     Using that $A(S)\succeq I_d$ we get that $\T{x_i}A(S)^{-1}x_i \leq
     \norm{x_i}_2^2 \leq 1$. Moreover, $\log(1+x)\geq x$ for all $x\leq 1$.
-    Hence:
+    Hence,
     \begin{displaymath}
         \partial_i F(\lambda) \geq
         \frac{1}{4}
-        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)^{-1}\bigg)x_i
+        \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:
@@ -355,7 +357,7 @@ In particular,
         \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i
         = \frac{1}{4}\T{x_i}\tilde{A}(\lambda)^{-1}x_i
          = \frac{1}{2}
-     \partial_i L(\lambda)
+     \partial_i L(\lambda).
     \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.
@@ -365,7 +367,7 @@ Having bound the ratio between the partial derivatives, we now bound the ratio $
     \begin{equation}\label{eq:lhopital}
         \frac{F(\lambda)}{L(\lambda)}
         = \frac{\partial_i F(\lambda)}{\partial_i
-        L(\lambda)} \geq \frac{1}{2}
+        L(\lambda)} \geq \frac{1}{2}.
     \end{equation}
     Second, 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:
@@ -391,37 +393,33 @@ Having bound the ratio between the partial derivatives, we now bound the ratio $
     function $V$. Hence, the ratio is equal to 1 on the vertices.
 \end{proof}
 
-\begin{proof}[of Lemma~\ref{lemma:relaxation}]
-Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*)
-    = OPT'$. 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(\lambda^*) \leq 2
-        F(\bar{\lambda})
-    \end{equation}
+To conclude the proof of Lemma~\ref{lemma:relaxation}, let us consider
+a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*) = OPT'$. 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(\lambda^*) \leq 2 F(\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$.
     By definition of the multi-linear extension $F$:
     \begin{displaymath}
-        F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\})
+        F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\}).
     \end{displaymath}
-    By submodularity of $V$, $V(S\cup\{i\})\leq V(S) + V(\{i\})$, hence:
+    By submodularity of $V$, $V(S\cup\{i\})\leq V(S) + V(\{i\})$. Hence,
     \begin{displaymath}
-        F(\bar{\lambda}) \leq V(S) + V(i)
+        F(\bar{\lambda}) \leq V(S) + V(i).
     \end{displaymath}
     Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and
-    $V(S)\leq OPT$. Hence:
+    $V(S)\leq OPT$. Hence,
     \begin{equation}\label{eq:e2}
-        F(\bar{\lambda}) \leq  OPT
-        + \max_{i\in\mathcal{N}} V(i)
+        F(\bar{\lambda}) \leq  OPT + \max_{i\in\mathcal{N}} V(i).
     \end{equation}
     Together, \eqref{eq:e1} and \eqref{eq:e2} imply the lemma. \hspace*{\stretch{1}}\qed
-\end{proof}
 
 \subsection{Proof of Theorem \ref{thm:lowerbound}}
 
-\begin{proof}
 Suppose, for contradiction, that such a mechanism exists. Consider two
 experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$
 and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must
@@ -430,6 +428,4 @@ a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity
 it remains in the solution; by  threshold payment, it is paid at least
 $B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility
 and individual rationality: hence, the selected set attains a value $\log2$,
-while the optimal value is $2\log 2$.
-\end{proof}
-
+while the optimal value is $2\log 2$.\hspace*{\stretch{1}}\qed