Approximation Algorithms for D-optimal Design

Abstract

Experimental design is a classical statistics problem and its aim is to estimate an unknown m-dimensional vector from linear measurements where a Gaussian noise is introduced in each measurement. For the combinatorial experimental design problem, the goal is to pick k out of the given n experiments so as to make the most accurate estimate of the unknown parameters, denoted as . In this paper, we will study one of the most robust measures of error estimation - D-optimality criterion, which corresponds to minimizing the volume of the confidence ellipsoid for the estimation error -. The problem gives rise to two natural variants depending on whether repetitions of experiments are allowed or not. We first propose an approximation algorithm with a 1e-approximation for the D-optimal design problem with and without repetitions, giving the first constant factor approximation for the problem. We then analyze another sampling approximation algorithm and prove that it is (1-)-approximation if k 4m+12^2(1) for any (0,1). Finally, for D-optimal design with repetitions, we study a different algorithm proposed by literature and show that it can improve this asymptotic approximation ratio.

Tasks

Reproductions