IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v171y2022ics0167947322000329.html
   My bibliography  Save this article

Computing minimum-volume enclosing ellipsoids for large datasets

Author

Listed:
  • Rosa, Samuel
  • Harman, Radoslav

Abstract

An algorithm is provided for calculating the minimum-volume enclosing ellipsoid (MVEE) for a large dataset stored in a separate database, for which the existing algorithms run out of memory or become prohibitively slow. The focus is on tall datasets, i.e., those consisting of huge numbers of data points of moderate dimensionality. The proposed Big Index Batching algorithm works in an optimization-deletion-adaptation cycle that consists of: using an existing algorithm by applying it on a smaller batch of data; pruning the vector of the indices of the data points by removing the points that are guaranteed to not lie on the boundary of the MVEE; and efficiently adapting the choice of the batch. The algorithm is provably convergent, and simple to describe and implement. The reading of tall data from the database is very time consuming, therefore the amount of reading during an MVEE computation should be as small as possible. It is shown on examples that Big Index Batching tends to find the MVEE after reading all data points just two or three times. As a consequence, the proposed algorithm usually converges to the MVEE reasonably fast. Its usefulness in robust statistics and anomaly detection is demonstrated by finding the potential outliers in a large dataset by using so-called ellipsoidal trimming.

Suggested Citation

  • Rosa, Samuel & Harman, Radoslav, 2022. "Computing minimum-volume enclosing ellipsoids for large datasets," Computational Statistics & Data Analysis, Elsevier, vol. 171(C).
    • Handle: RePEc:eee:csdana:v:171:y:2022:i:c:s0167947322000329
    DOI: 10.1016/j.csda.2022.107452
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167947322000329
    Download Restriction: Full text for ScienceDirect subscribers only.
    File URL: https://libkey.io/10.1016/j.csda.2022.107452?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Pronzato, Luc, 2013. "A delimitation of the support of optimal designs for Kiefer’s ϕp-class of criteria," Statistics & Probability Letters, Elsevier, vol. 83(12), pages 2721-2728.
    2. D. M. Titterington, 1978. "Estimation of Correlation Coefficients by Ellipsoidal Trimming," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 27(3), pages 227-234, November.
    3. Harman, Radoslav & Pronzato, Luc, 2007. "Improvements on removing nonoptimal support points in D-optimum design algorithms," Statistics & Probability Letters, Elsevier, vol. 77(1), pages 90-94, January.
    4. Peng Sun & Robert M. Freund, 2004. "Computation of Minimum-Volume Covering Ellipsoids," Operations Research, INFORMS, vol. 52(5), pages 690-706, October.
    5. Samuel Rosa & Radoslav Harman, 2016. "Optimal approximate designs for estimating treatment contrasts resistant to nuisance effects," Statistical Papers, Springer, vol. 57(4), pages 1077-1106, December.
    6. Min Yang & Stefanie Biedermann & Elina Tang, 2013. "On Optimal Designs for Nonlinear Models: A General and Efficient Algorithm," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 108(504), pages 1411-1420, December.
    7. P. Kumar & E. A. Yildirim, 2005. "Minimum-Volume Enclosing Ellipsoids and Core Sets," Journal of Optimization Theory and Applications, Springer, vol. 126(1), pages 1-21, July.
    8. Radoslav Harman & Lenka Filová & Peter Richtárik, 2020. "A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 115(529), pages 348-361, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Karim Abou-Moustafa & Frank P. Ferrie, 2018. "Local generalized quadratic distance metrics: application to the k-nearest neighbors classifier," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 12(2), pages 341-363, June.
    2. Harman, Radoslav & Rosa, Samuel, 2019. "Removal of the points that do not support an E-optimal experimental design," Statistics & Probability Letters, Elsevier, vol. 147(C), pages 83-89.
    3. Lianyan Fu & Faming Ma & Zhuoxi Yu & Zhichuan Zhu, 2023. "Multiplication Algorithms for Approximate Optimal Distributions with Cost Constraints," Mathematics, MDPI, vol. 11(8), pages 1-14, April.
    4. Yu, Yaming, 2010. "Strict monotonicity and convergence rate of Titterington's algorithm for computing D-optimal designs," Computational Statistics & Data Analysis, Elsevier, vol. 54(6), pages 1419-1425, June.
    5. Duarte, Belmiro P.M. & Atkinson, Anthony C. & Granjo, Jose F.O & Oliveira, Nuno M.C, 2019. "Optimal design of experiments for liquid–liquid equilibria characterization via semidefinite programming," LSE Research Online Documents on Economics 102500, London School of Economics and Political Science, LSE Library.
    6. Haoyu Wang & Chongqi Zhang, 2022. "The mixture design threshold accepting algorithm for generating $$\varvec{D}$$ D -optimal designs of the mixture models," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 85(3), pages 345-371, April.
    7. Dette, Holger & Pepelyshev, Andrey & Zhigljavsky, Anatoly, 2008. "Improving updating rules in multiplicative algorithms for computing D-optimal designs," Computational Statistics & Data Analysis, Elsevier, vol. 53(2), pages 312-320, December.
    8. Radoslav Harman & Eva Benková, 2017. "Barycentric algorithm for computing D-optimal size- and cost-constrained designs of experiments," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 80(2), pages 201-225, February.
    9. Duarte, Belmiro P.M. & Atkinson, Anthony C. & Granjo, Jose F.O & Oliveira, Nuno M.C, 2022. "Optimal design of experiments for implicit models," LSE Research Online Documents on Economics 107584, London School of Economics and Political Science, LSE Library.
    10. Guillaume Sagnol & Edouard Pauwels, 2019. "An unexpected connection between Bayes A-optimal designs and the group lasso," Statistical Papers, Springer, vol. 60(2), pages 565-584, April.
    11. Yu, Jun & Meng, Xiran & Wang, Yaping, 2023. "Optimal designs for semi-parametric dose-response models under random contamination," Computational Statistics & Data Analysis, Elsevier, vol. 178(C).
    12. Àngela Sebastià Bargues & José-Luis Polo Sanz & Raúl Martín Martín, 2022. "Optimal Experimental Design for Parametric Identification of the Electrical Behaviour of Bioelectrodes and Biological Tissues," Mathematics, MDPI, vol. 10(5), pages 1-16, March.
    13. Wei-jie Cong & Le Wang & Hui Sun, 2020. "Rank-two update algorithm versus Frank–Wolfe algorithm with away steps for the weighted Euclidean one-center problem," Computational Optimization and Applications, Springer, vol. 75(1), pages 237-262, January.
    14. Peter Goos & Bradley Jones & Utami Syafitri, 2016. "I-Optimal Design of Mixture Experiments," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 111(514), pages 899-911, April.
    15. Selin Ahipaşaoğlu, 2015. "Fast algorithms for the minimum volume estimator," Journal of Global Optimization, Springer, vol. 62(2), pages 351-370, June.
    16. Samuel Rosa, 2018. "Optimal designs for treatment comparisons represented by graphs," AStA Advances in Statistical Analysis, Springer;German Statistical Society, vol. 102(4), pages 479-503, October.
    17. Dette, Holger & Pepelyshev, Andrey & Zhigljavsky, Anatoly, 2007. "Improving updating rules in multiplicativealgorithms for computing D-optimal designs," Technical Reports 2007,28, Technische Universität Dortmund, Sonderforschungsbereich 475: Komplexitätsreduktion in multivariaten Datenstrukturen.
    18. Belmiro P. M. Duarte, 2023. "Exact Optimal Designs of Experiments for Factorial Models via Mixed-Integer Semidefinite Programming," Mathematics, MDPI, vol. 11(4), pages 1-17, February.
    19. Gauthier, B. & Pronzato, L., 2017. "Convex relaxation for IMSE optimal design in random-field models," Computational Statistics & Data Analysis, Elsevier, vol. 113(C), pages 375-394.
    20. Nolan, D., 1999. "On min-max majority and deepest points," Statistics & Probability Letters, Elsevier, vol. 43(4), pages 325-333, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:csdana:v:171:y:2022:i:c:s0167947322000329. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/csda .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.