Abstract
We study the optimal design problems where the goal is to choose a set oflinear measurements to obtain the most accurate estimate of an unknown vectorin $d$ dimensions. We study the $A$-optimal design variant where the objectiveis to minimize the average variance of the error in the maximum likelihoodestimate of the vector being measured. The problem also finds applications insensor placement in wireless networks, sparse least squares regression, featureselection for $k$-means clustering, and matrix approximation. In this paper, weintroduce proportional volume sampling to obtain improved approximationalgorithms for $A$-optimal design. Our main result is to obtain improvedapproximation algorithms for the $A$-optimal design problem by introducing theproportional volume sampling algorithm. Our results nearly optimal bounds inthe asymptotic regime when the number of measurements done, $k$, issignificantly more than the dimension $d$. We also give first approximationalgorithms when $k$ is small including when $k=d$. The proportionalvolume-sampling algorithm also gives approximation algorithms for other optimaldesign objectives such as $D$-optimal design and generalized ratio objectivematching or improving previous best known results. Interestingly, we show thata similar guarantee cannot be obtained for the $E$-optimal design problem. Wealso show that the $A$-optimal design problem is NP-hard to approximate withina fixed constant when $k=d$.