Urbana Campus Research Calendar

Back to Listing

ISE Seminar-Approximation Algorithms for D-optimal Design

Event Type
Industrial & Enterprise Systems Engineering
303 Transportation Building
Dec 6, 2017   2:00 pm  
Weijun Xie, Virginia Tech
Originating Calendar
ISE Seminar Calendar


Experimental design is a classical problem in statistics. In the experimental design problem, the aim is to estimate an unknown vector x from linear measurements where a Gaussian noise is introduced in each measurement. The goal is to pick k out of the given n experiments so as to make the most accurate estimate of the unknown parameter x. Given a set S of chosen experiments, the most likelihood estimate x' can be obtained by a least squares computation. One of the robust measures of error estimation is the D-optimality criterion which aims to minimize the generalized variance of the estimator. This corresponds to minimizing the volume of the standard confidence ellipsoid for the estimation error x-x'. The problem gives rise to two natural variants depending on whether repetitions are allowed or not. The latter variant, while being more general, has also found applications in the geographical location of sensors. In this work, we prove a 1/e-approximation for the D-optimal design problem with and without repetitions, providing the first constant factor approximation for the problem. We also consider the case when the number of experiments chosen is much larger than the dimension of the measurements and provide an asymptotically optimal approximation algorithm. This is a joint work with Dr. Mohit Singh from Georgia Tech.


Dr. Weijun Xie graduated from Georgia Tech in August 2017 and now is Assistant Professor in the Department of Industrial and Systems Engineering at Virginia Tech. His research interests are in theory and applications of stochastic, discrete and convex optimization. One of his recent paper received Honorable mention in George Nicholson Student Paper Competition at INFORMS 2017.

link for robots only