From d0349ca6b30e11915cd95c00e981e712198fb5da Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Wed, 31 Oct 2012 11:19:12 -0700
Subject: lower bound

---
 problem.tex | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
index 5fd8906..423e6fa 100644
--- a/problem.tex
+++ b/problem.tex
@@ -17,12 +17,13 @@ Note that the estimator $\hat{\beta}$ is a linear map of $y_S$; as $y_S$ is a mu
  
 Let $V:2^\mathcal{N}\to\reals$ be a value function, quantifying how informative a set of experiments $S$ is in estimating $\beta$. The standard optimal experimental design problem amounts to finding a set $S$ that maximizes $V(S)$ subject to the constraint $|S|\leq k$. 
 
-There is a variety of different value functions used in experimental design~\cite{pukelsheim2006optimal}; almost all are related to the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. Due to its relationship to entropy,  the \emph{$D$-optimality criterion} is commonly used: %which yields the following optimization problem
+A variety of different value functions are used in experimental design~\cite{pukelsheim2006optimal}; almost all are related to the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. A commonly used choice is the so-called \emph{$D$-optimality criterion} \cite{pukelsheim2006optimal,chaloner1995bayesian}: %which yields the following optimization problem
 \begin{align}
  V(S) &= \frac{1}{2}\log\det \T{X_S}X_S \label{dcrit} %\\
 \end{align}
 As $\hat{\beta}$ is a multidimensional normal random variable, the $D$-optimality criterion is equal (up to a costant) to the negative of the entropy of $\hat{\beta}$. Hence,  maximizing \eqref{dcrit} amounts to finding the set of experiments that minimizes the uncertainty on $\beta$, as captured by the entropy of its estimator.
 
+Value function \eqref{dcrit} has several appealing properties. To begin with, it is a submodular set function (see Lemma~\ref{...} and Thm.~\ref{...}). In addition, the maximization of convex relaxations of this function is a  well-studied problem \cite{boyd}. Note that \eqref{dcrit} is undefined when $\mathrm{rank}(\T{X_S}X_S)<d$; in this case, we take $V(S)=-\infty$ (so that $V$ takes values in the extended reals).
 %As discussed in the next section, in this paper, we work with a modified measure of information function, namely 
 %\begin{align}
 %V(S) & = \frac{1}{2} \log\det \left(I + \T{X_S}X_S\right)
-- 
cgit v1.2.3-70-g09d2