We study the $A$-optimal design problem where we are given vectors $v_1,\ldots,v_n\in\mathbb{R}^d$, an integer $k\geq d$, and the goal is to select a set $S$ of $k$ vectors that minimizes the trace of $(\sum_{i\in S}v_iv_i^\top)^{-1}$. Traditionally, the problem is an instance of optimal design of experiments in statistics where each vector corresponds to a linear measurement of an unknown vector and the goal is to pick $k$ of them that minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placement in wireless networks, sparse least squares regression, feature selection for $k$-means clustering, and matrix approximation. In this paper, we introduce proportional volume sampling to obtain improved approximation algorithms for $A$-optimal design. Given a matrix, proportional volume sampling picks a set of columns $S$ of size $k$ with probability proportional to $\mu(S)$ times $\det(\sum_{i\in S}v_iv_i^\top)$ for some measure $\mu$. Our main result is to show the approximability of the $A$-optimal design problem can be reduced to approximate independence properties of the measure $\mu$. We appeal to hard-core distributions as candidate distributions $\mu$ that allow us to obtain improved approximation algorithms for the $A$-optimal design. Our results include a $d$-approximation when $k=d$, an $(1+\epsilon)$-approximation when $k=\Omega\left(\frac{d}{\epsilon}+\frac{1}{\epsilon^2}\log\frac{1}{\epsilon}\right)$ and $\frac{k}{k-d+1}$-approximation when repetitions of vectors are allowed in the solution. We consider generalization of the problem for $k\leq d$ and obtain a $k$-approximation. The last result implies a restricted invertibility principle for the harmonic mean of singular values. We also show that the problem is $\mathsf{NP}$-hard to approximate within a fixed constant when $k=d$.

本文介绍了使用比例体积抽样算法来获得$A$-最优设计的改进近似算法，特别是在测量次数$k$显着大于维度$d$的渐进区域内，我们的结果几乎是最优的。同时，我们还证明了当k=d时，$A$-最优设计问题的近似难度是NP-hard的。本文的主要应用场景包括无线网络中的传感器放置，稀疏最小二乘回归，$k$-means聚类的特征选择和矩阵近似等方面。

比例体积采样和逼近算法在A-最优设计中的应用