%ASingh, Mohit%AXie, Weijun%BJournal Name: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
%D2018%I
%JJournal Name: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
%K
%MOSTI ID: 10065985
%PMedium: X; Size: 2240-2255
%TApproximate Positive Correlated Distributions and Approximation Algorithms for D-optimal Design
%XExperimental design is a classical area in statistics and has also found new applications in machine learning. In the combinatorial experimental design problem, the aim is to estimate an unknown m-dimensional 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 x0 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 − x0. The problem gives rise to two natural variants depending on whether repetitions of experiments is allowed or not. The latter variant, while being more general, has also found
applications in geographical location of sensors.
We show a close connection between approximation algorithms for the D-optimal design problem and constructions of approximately m-wise positively correlated distributions.
This connection allows us to obtain first approximation algorithms for the D-optimal design problem with and without repetitions. We then consider the case when the number of experiments chosen is much larger than the dimension m and show one can obtain asymptotically optimal algorithms in this case.
%0Journal Article
Country unknown/Code not availablehttps://doi.org/10.1137/1.9781611975031.145OSTI-MSA