Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: Scalable Algorithms and Performance Guarantees

References

• Alarifi A, AlZubi AA, Al-Maitah M, Al-Kasasbeh B (2019) An optimal sensor placement algorithm (O-SPA) for improving tracking precision of human activity in real-world healthcare systems. Comput. Comm. 148:9–16.Crossref, Google Scholar
• Alon N, Spencer JH (2016) The Probabilistic Method (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Anstreicher KM (2018) Maximum-entropy sampling and the Boolean quadric polytope. J. Global Optim. 72(4):603–618.Crossref, Google Scholar
• Anstreicher KM (2020) Efficient solution of maximum-entropy sampling problems. Oper. Res. 68(6):1826–1835.Link, Google Scholar
• Anstreicher KM, Lee J (2004) A masked spectral bound for maximum-entropy sampling. mODa 7—Advances in Model-Oriented Design and Analysis (Springer, Berlin), 1–12.Crossref, Google Scholar
• Anstreicher KM, Fampa M, Lee J, Williams J (1996) Continuous relaxations for constrained maximum-entropy sampling. Integer Programming Combin. Optim.: 5th Internat. IPCO Conf. Proc., vol. 5 (Springer, Berlin, Heidelberg), 234–248.Google Scholar
• Anstreicher KM, Fampa M, Lee J, Williams J (1999) Using continuous nonlinear relaxations to solve constrained maximum-entropy sampling problems. Math. Programming 85(2):221–240.Crossref, Google Scholar
• Arellano-Valle RB, Contreras-Reyes JE, Genton MG (2013) Shannon entropy and mutual information for multivariate skew-elliptical distributions. Scandinavian J. Statist. 40(1):42–62.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2012) Optimization III: Convex analysis, nonlinear programming theory, nonlinear programming algorithms. Lecture Notes, 34.Google Scholar
• Bertsekas DP (1982) Constrained Optimization and Lagrange Multiplier Methods (Academic Press, Cambridge, MA).Google Scholar
• Bueso M, Angulo J, Alonso F (1998) A state-space model approach to optimum spatial sampling design based on entropy. Environ. Ecological Statist. 5(1):29–44.Crossref, Google Scholar
• Burer S, Lee J (2007) Solving maximum-entropy sampling problems using factored masks. Math. Programming 109(2–3):263–281.Crossref, Google Scholar
• Charikar M, Guruswami V, Kumar R, Rajagopalan S, Sahai A (2000) Combinatorial feature selection problems. Proc. 41st Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 631–640.Google Scholar
• Christodoulou S (2015) Smarting up water distribution networks with an entropy-based optimal sensor placement strategy. J. Smart Cities 1(1):47–58.Google Scholar
• Çivril A, Magdon-Ismail M (2009) On selecting a maximum volume sub-matrix of a matrix and related problems. Theoretical Comput. Sci. 410(47–49):4801–4811.Crossref, Google Scholar
• Çivril A, Magdon-Ismail M (2013) Exponential inapproximability of selecting a maximum volume sub-matrix. Algorithmica 65(1):159–176.Crossref, Google Scholar
• Cover TM, Thomas JA (2012) Elements of Information Theory (John Wiley & Sons, Hoboken, NJ).Google Scholar
• de Aguiar PF, Bourguignon B, Khots M, Massart D, Phan-Than-Luu R (1995) D-optimal designs. Chemometrics Intelligent Laboratory Systems 30(2):199–210.Crossref, Google Scholar
• Derezinski M, Warmuth MK (2017) Unbiased estimates for linear regression via volume sampling. Adv. Neural Inform. Processing Systems (NeurIPS, San Diego), 3084–3093.Google Scholar
• Dey SS, Mazumder R, Wang G (2022) Using ℓ1-relaxation and integer programming to obtain dual bounds for sparse PCA. Oper. Res. 70(3):1914–1932.Link, Google Scholar
• Freund RM, Grigas P (2016) New analysis and results for the Frank–Wolfe method. Math. Programming 155(1–2):199–230.Crossref, Google Scholar
• Gilmore CJ (1996) Maximum entropy and Bayesian statistics in crystallography: A review of practical applications. Acta Crystallographica Section A 52(4):561–589.Crossref, Google Scholar
• Hazimeh H, Mazumder R (2020) Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms. Oper. Res. 68(5):1517–1537.Link, Google Scholar
• Hoch JC, Maciejewski MW, Mobli M, Schuyler AD, Stern AS (2014) Nonuniform sampling and maximum entropy reconstruction in multidimensional NMR. Accounts Chemical Res. 47(2):708–717.Crossref, Google Scholar
• Hoffman A, Lee J, Williams J (2001) New upper bounds for maximum-entropy sampling. mODa 6—Advances in Model-Oriented Design and Analysis (Springer, Berlin), 143–153.Crossref, Google Scholar
• Hou SH (1998) Classroom note: A simple proof of the Leverrier–Faddeev characteristic polynomial algorithm. SIAM Rev. 40(3):706–709.Crossref, Google Scholar
• Jaynes ET (1957) Information theory and statistical mechanics. Physical Rev. 106(4):620.Crossref, Google Scholar
• Kelmans AK, Kimelfeld B (1983) Multiplicative submodularity of a matrix’s principal minor as a function of the set of its rows and some combinatorial applications. Discrete Math. 44(1):113–116.Crossref, Google Scholar
• Ko CW, Lee J, Queyranne M (1995) An exact algorithm for maximum entropy sampling. Oper. Res. 43(4):684–691.Link, Google Scholar
• Lee J (1998) Constrained maximum-entropy sampling. Oper. Res. 46(5):655–664.Link, Google Scholar
• Lee J, Williams J (2003) A linear integer programming bound for maximum-entropy sampling. Math. Programming 94(2–3):247–256.Crossref, Google Scholar
• Lemaréchal C, Renaud A (2001) A geometric study of duality gaps, with applications. Math. Programming 90(3):399–427.Crossref, Google Scholar
• Lewis A (1995) The convex analysis of unitarily invariant matrix functions. J. Convex Anal. 2(1/2):173–183.Google Scholar
• Li Q, Cui T, Weng Y, Negi R, Franchetti F, Ilic MD (2012) An information-theoretic approach to PMU placement in electric power systems. IEEE Trans. Smart Grid 4(1):446–456.Crossref, Google Scholar
• Lin M, Trudinger NS (1994) On some inequalities for elementary symmetric functions. Bull. Australian Math. Soc. 50(2):317–326.Crossref, Google Scholar
• Madan V, Singh M, Tantipongpipat U, Xie W (2019) Combinatorial algorithms for optimal design. Conf. Learn. Theory, 2210–2258.Google Scholar
• Moreno-Salinas D, Pascoal A, Aranda J (2013) Sensor networks for optimal target localization with bearings-only measurements in constrained three-dimensional scenarios. Sensors (Basel) 13(8):10386–10417.Crossref, Google Scholar
• Nikolov A (2015) Randomized rounding for the largest simplex problem. Proc. 47th Annual ACM Sympos. Theory Comput. (ACM, New York), 861–870.Google Scholar
• Nikolov A, Singh M, Tantipongpipat UT (2019) Proportional volume sampling and approximation algorithms for A-optimal design. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1369–1386.Google Scholar
• O’Flynn B, Regan F, Lawlor A, Wallace J, Torres J, O’Mathuna C (2010) Experiences and recommendations in deploying a real-time, water quality monitoring system. Measurement Sci. Tech. 21(12):124004.Crossref, Google Scholar
• Pedregosa F, Askari A, Negiar G, Jaggi M (2018) Step-size adaptivity in projection-free optimization. Preprint, submitted June 13, https://arxiv.org/abs/1806.05123.Google Scholar
• Pukelsheim F (2006) Optimal Design of Experiments (SIAM, Philadelphia).Crossref, Google Scholar
• Rigau J, Feixas M, Sbert M (2003) Entropy-based adaptive sampling. Graphics Interface 2:79–87.Google Scholar
• Rockafellar RT (1970) Convex Analysis, vol. 28 (Princeton University Press).Crossref, Google Scholar
• Schmieder P, Stern AS, Wagner G, Hoch JC (1993) Application of nonlinear sampling schemes to COSY-type spectra. J. Biomolecular NMR. 3(5):569–576.Crossref, Google Scholar
• Sharma D, Kapoor A, Deshpande A (2015) On greedy maximization of entropy. Internat. Conf. Machine Learn., 1330–1338.Google Scholar
• Shewry MC, Wynn HP (1987) Maximum entropy sampling. J. Appl. Statist. 14(2):165–170.Crossref, Google Scholar
• Singh M, Xie W (2018) Approximate positive correlated distributions and approximation algorithms for d-optimal design. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2240–2255.Google Scholar
• Singh M, Xie W (2020) Approximation algorithms for d-optimal design. Math. Oper. Res. 45(4):1512–1534.Link, Google Scholar
• Song Y, Liò P (2010) A new approach for epileptic seizure detection: Sample entropy based feature extraction and extreme learning machine. J. Biomedical Sci. Engrg. 3(6):556–567.Crossref, Google Scholar
• Summa MD, Eisenbrand F, Faenza Y, Moldenhauer C (2014) On largest volume simplices and sub-determinants. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 315–323.Google Scholar
• Wang Y, Zhang L, Chen G (2019) Optimal sensor placement for obstacle detection of manipulator based on relative entropy. 14th IEEE Conf. Indust. Electronics Appl. (IEEE, Piscataway, NJ), 702–707.Google Scholar
• Xu S, Doğançay K (2017) Optimal sensor placement for 3-D angle-of-arrival target localization. IEEE Trans. Aerospace Electronic Systems 53(3):1196–1211.Crossref, Google Scholar
• Yao Y, Wang H (2019) Optimal subsampling for softmax regression. Statist. Papers 60(2):235–249.Crossref, Google Scholar
• Zilly J, Buhmann JM, Mahapatra D (2017) Glaucoma detection using entropy sampling and ensemble learning for automatic optic cup and disc segmentation. Comput. Medical Imaging Graphics 55:28–41.Crossref, Google Scholar