Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design
Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design
复制标题
A 最优设计的比例体积采样和近似算法
DOI：
10.1137/1.9781611975482.84
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Tantipongpipat, U.
中科院分区：
文献类型：
--
作者：
Nikolov, A;Singh, M.;Tantipongpipat, U.
我们研究最优设计问题，其目标是选择一组线性测量以获得未知向量的最准确估计。我们研究最优设计变体，其目标是最小化被测量向量的最大似然估计中的误差的平均方差。我们引入比例体积采样算法，以便在测量次数显着大于维数时在渐近状态下获得接近最优的边界，并获得第一近似算法，当可能的测量次数很小时，其近似因子不会随着可能的测量次数而降低。该算法还为其他最优设计目标（例如最优性和广义比率目标）提供近似保证，匹配或改进先前最知名的结果。我们进一步表明，对于最优设计来说，无法获得与我们的边界类似的边界，并且当最优设计在固定常数内难以近似时，NP 很难。
We study optimal design problems in which the goal is to choose a set of linear measurements to obtain the most accurate estimate of an unknown vector. We study the-optimal design variant where the objective is to minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. We introduce theproportional volume samplingalgorithm to obtain nearly optimal bounds in the asymptotic regime when the numberof measurements made is significantly larger than the dimensionand obtain the first approximation algorithms whose approximation factor does not degrade with the number of possible measurements whenis small. The algorithm also gives approximation guarantees for other optimal design objectives such as-optimality and the generalized ratio objective, matching or improving the previously best-known results. We further show that bounds similar to ours cannot be obtained for-optimal design and that-optimal design is NP-hard to approximate within a fixed constant when.
登录
查看更多内容
受限可逆性和到立方体的 Banach-Mazur 距离
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Pierre Youssef
通讯作者：
Pierre Youssef
D 最优设计的近似正相关分布和近似算法
DOI：
--
发表时间：
2018
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Mohit Singh;Weijun Xie
通讯作者：
Weijun Xie
DOI：
10.1006/jctb.1996.0067
发表时间：
1996-11
期刊：
J. Comb. Theory, Ser. B
影响因子：
--
作者：
J. Kahn
通讯作者：
J. Kahn
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
D. Spielman;N. Srivastava
通讯作者：
N. Srivastava
DOI：
10.1137/1.9781611973730.24
发表时间：
2013
期刊：
ArXiv
影响因子：
--
作者：
Aleksandar Nikolov;Kunal Talwar
通讯作者：
Kunal Talwar