Approximation Algorithms for D-optimal Design

References

• [1] Albert I, Denis J-B (2011) Dirichlet and multinomial distributions: Properties and uses in Jags. Anal. (Oxford) 31:1141–1155.Google Scholar
• [2] Allen-Zhu Z, Liao Z, Orecchia L (2015) Spectral sparsification and regret minimization beyond matrix multiplicative updates. Proc. 47th Annual ACM Sympos. Theory Comput. (ACM, New York), 237–245.Google Scholar
• [3] Allen-Zhu Z, Li Y, Singh A, Wang Y (2017) Near-optimal design of experiments via regret minimization. Proc. 34th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 70 (PMLR), 126–135.Google Scholar
• [4] Anari N, Gharan SO (2017) A generalization of permanent inequalities and applications in counting and optimization. Preprint, submitted February 9, https://arxiv.org/abs/1702.02937.Google Scholar
• [5] Atkinson AC, Donev AN, Tobias RD (2007) Optimum Experimental Designs, with SAS, vol. 34 (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• [6] Avron H, Boutsidis C, Toledo S, Zouzias A (2013) Efficient dimensionality reduction for canonical correlation analysis. Proc. 30th Internat. Conf. Machine Learn. (ICML-13), Proceedings Machine Learning Research, vol. 28(PMLR), 347–355.Google Scholar
• [7] Batson J, Spielman DA, Srivastava N (2012) Twice-ramanujan sparsifiers. SIAM J. Comput. 41(6):1704–1721.Crossref, Google Scholar
• [8] Ben-Tal A, Nemirovski A (2001) Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, vol. 2 (SIAM, Philadelphia).Crossref, Google Scholar
• [9] Bouhtou M, Gaubert S, Sagnol G (2010) Submodularity and randomized rounding techniques for optimal experimental design. Electronic Notes Discrete Math. 36:679–686.Crossref, Google Scholar
• [10] Brändén P, Jonasson J (2012) Negative dependence in sampling. Scandinavian J. Statist. 39(4):830–838.Crossref, Google Scholar
• [11] Brewer KRW, Hanif M (2013) Sampling with Unequal Probabilities, vol. 15 (Springer Science & Business Media, New York).Google Scholar
• [12] Broida JG, Williamson SG (1989) A Comprehensive Introduction to Linear Algebra (Addison-Wesley, Reading, MA).Google Scholar
• [13] Byrka J, Pensyl T, Rybicki B, Srinivasan A, Trinh K (2014) An improved approximation for k-median, and positive correlation in budgeted optimization. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 737–756.Google Scholar
• [14] Calinescu G, Chekuri C, Pál M, Vondrák J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6):1740–1766.Crossref, Google Scholar
• [15] Chernoff H (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 493–507.Crossref, Google Scholar
• [16] Cooley JW, Tukey JW (1965) An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19(90):297–301.Crossref, Google Scholar
• [17] Di Summa M, Eisenbrand F, Faenza Y, Moldenhauer C (2015) On largest volume simplices and sub-determinants. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 315–323.Google Scholar
• [18] Federer WT (1955) Experimental Design (Macmillan Co., New York).Google Scholar
• [19] Fedorov VV (1972) Theory of Optimal Experiments (Academic Press, New York).Google Scholar
• [20] Horn RA, Johnson CR (1985) Matrix Analysis (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [21] Hou S-H (1998) Classroom note: A simple proof of the Leverrier–Faddeev characteristic polynomial algorithm. SIAM Rev. 40(3):706–709.Crossref, Google Scholar
• [22] Joshi S, Boyd S (2009) Sensor selection via convex optimization. IEEE Trans. Signal Processing 57(2):451–462.Crossref, Google Scholar
• [23] Khachiyan LG (1996) Rounding of polytopes in the real number model of computation. Math. Oper. Res. 21(2):307–320.Link, Google Scholar
• [24] Kirk RE (1982) Experimental Design (John Wiley & Sons, New York).Google Scholar
• [25] Krause A, Golovin D (2014) Submodular function maximization. Accessed November 25, 2019, http://www.cs.cmu.edu/afs/.cs.cmu.edu/Web/People/dgolovin/papers/submodular_survey12.pdf.Google Scholar
• [26] Lin M, Trudinger NS (1994) On some inequalities for elementary symmetric function. Bull. Australian Math. Soc. 50(2):317–326.Google Scholar
• [27] Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• [28] Nikolov A (2015) Randomized rounding for the largest simplex problem. Proc. 47th Annual ACM Sympos. Theory Comput. (ACM, New York), 861–870.Google Scholar
• [29] Nikolov A, Singh M (2016) Maximizing determinants under partition constraints. Proc. 48th Annual ACM Sympos. Theory Comput. (ACM, New York), 192–201.Crossref, Google Scholar
• [30] Nikolov A, Singh M, Tantipongpipat UT (2018) Proportional volume sampling and approximation algorithms for A-optimal design. Preprint, submitted February 22, https://arxiv.org/abs/1802.08318.Google Scholar
• [31] Papoulis A, Unnikrishna Pillai S (2002) Probability, Random Variables, and Stochastic Processes (Tata McGraw-Hill Education, New York).Google Scholar
• [32] Pukelsheim F (2006) Optimal Design of Experiments (SIAM, Philadelphia).Crossref, Google Scholar
• [33] Sagnol G, Harman R (2015) Computing exact D-optimal designs by mixed integer second-order cone programming. Ann. Statist. 43(5):2198–2224.Crossref, Google Scholar
• [34] Shamaiah M, Banerjee S, Vikalo H (2010) Greedy sensor selection: Leveraging submodularity. Proc. 49th IEEE Conf. Decision Control (CDC) (IEEE, New York), 2572–2577.Google Scholar
• [35] Singh M, Xie W (2018) Approximate positively correlated distributions and approximation algorithms for D-optimal design. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2240–2255.Google Scholar
• [36] Spencer JH, Spencer JH (1987) Ten Lectures on the Probabilistic Method, vol. 52 (SIAM, Philadelphia).Google Scholar
• [37] Spielman DA, Srivastava N (2011) Graph sparsification by effective resistances. SIAM J. Comput. 40(6):1913–1926.Crossref, Google Scholar
• [38] Straszak D, Vishnoi NK (2016) Real stable polynomials and matroids: Optimization and counting. Preprint, submitted November 14, https://arxiv.org/abs/1611.04548.Google Scholar
• [39] Wang Y, Yu AW, Singh A (2016) On computationally tractable selection of experiments in regression models. Preprint, submitted January 9, https://arxiv.org/abs/1601.02068.Google Scholar
• [40] Welch WJ (1982) Algorithmic complexity: Three NP-hard problems in computational statistics. J. Statist. Comput. Simulation 15(1):17–25.Crossref, Google Scholar
• [41] Xu J (2008) Generalized Newton-like inequalities. J. Inequalities Pure Appl. Math. 9(3), Paper No. 85.Google Scholar