Heuristic Approaches to Constructing a Minimum Volume Ellipsoid around a Subset of Points

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

The paper deals with the following essentially combinatorial problem: Given N points in ℝn, compose the ellipsoid of minimum volume containing exactly N – k points where k is much less than N. Six algorithms for an approximate solution of this problem are proposed; they are based on certain heuristic considerations. Under various assumptions on the mechanism of generating the points and their amount, the comparative efficiency of the algorithms was conducted and the results of numerical experiments were presented.

About the authors

Pavel S. Shcherbakov

V. A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences; Moscow Institute of Physics and Technology; Federal Research Center «Informatics and Control», Russian Academy of Sciences

Author for correspondence.
Email: cavour118@mail.ru

главный научный сотрудник, доктор физико-математических наук; ведущий научный сотрудник; ведущий научный сотрудник

Russian Federation, Moscow; Dolgoprudny; Moscow

Yana I. Kvinto

V. A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Email: yanakvinto@mail.ru

старший научный сотрудник, кандидат технических наук

Russian Federation, Moscow

References

  1. Becker S., Bobin J., Candes E. NESTA: A fast and accurate first-order method for sparse recovery. SIAM J. on Imaging Sciences. 2009;4(1):1–39.
  2. Burke E.K., Kendall G. (eds.) Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. New York: Springer Science+Business Media, 2014.
  3. Donoho D.L. For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics. 2006;56(6):797–829.
  4. Ruan D., Chen G., Kerre E.E., Wets G. (eds.) Intelligent Data Mining: Techniques and Applications. Studies in Computational Intelligence. Vol. 5. New York: Springer, 2005.
  5. Ahipaşaoğlu S.D. Fast algorithms for the minimum volume estimator. Journal of Global Optimization. 2015;62(2):351–370.
  6. Boyd S., El Ghaoui L., Feron E., Balakrishnan V. Linear Matrix Inequalities in System and Control Theory. Philadelphia: SIAM, 1994.
  7. Boyd S., Vandenberge L. Convex Optimization. Cambridge, MA: Cambridge University Press, 2004.
  8. Grant M., Boyd S. CVX: Matlab software for disciplined convex programming, ver. 2.2. Available from: http://stanford.edu/~boyd/cvx, 2020.
  9. Ahipaşaoğlu S.D., Sun P., Todd M.J. Linear convergence of a modified frank-wolfe algorithm for computing minimum-volume enclosing ellipsoids. Optimization Methods and Software. 2008;23:5–19.
  10. Sun P., Freund R.M. Computation of minimum-volume covering ellipsoids. Operations Research. 2004;52(5): 690–706.
  11. Agullo J. Exact iterative computation of the multivariate minimum volume ellipsoid estimator with a branch and bound algorithm. In: Pratt A. (ed.) Proceedings in Computational Statistics. Heidelberg; Physica-Verlag, 1996. p. 175–180.
  12. Bai E.-W., Chi H., Tempo R., Ye Y. Optimization with few violated constraints for linear bounded error parameter estimation. IEEE Trans. Autom. Control. 2002;47(7):1067–1077.
  13. Dabbene F., Shcherbakov P. Minimum volume ellipsoid comprising a subset of points. In: Proceedings of the 6th Int. Conf. Control, Decision Inform. Technologies (CoDiT 2019), Paris, Apr 23–26, 2019, paper WiP 20
  14. Gärtner B. Sampling with removal in LP-type problems. Journal of Computational Geometry. 2015;6(2):93–112.
  15. Tempo R., Calafiore G., Dabbene F. Randomized Algorithms for Analysis and Control of Uncertain Systems: With Applications. 2nd ed. Springer, 2013.
  16. Van Aelst S., Rousseeuw P. Minimum volume ellipsoid. WIREs Computational Statistics. 2009;1:71–82.
  17. Campi M.C., Garatti S. A sampling-and-discarding approach to chance-constrained optimization: Feasibility and optimality. Journal of Optimization Theory and Applications.2011;148:257–280.
  18. Dabbene F., Henrion D., Lagoa C., Shcherbakov P. Randomized approximations of the image set of nonlinear discrete-time systems with applications to filtering. In: Proceedings of the 8th IFAC Symposium on Robust Control Design (ROCOND 2015), Bratislava, Slovak Republic, Jul 8–11, 2015.
  19. Raynaud H. Sur l’enveloppe convexe des nuages de points aleatoires dans IRn. I. Journal of Applied Probability. 1970;7(1):35–48.
  20. Hueter I. Limit theorems for the convex hull of random points in higher dimensions. Trans. Amer. Math. Soc. 1999;351(11):4337–4363.
  21. Jolliffe I.T. Principal Component Analysis. Springer Series in Statistics. New York: Springer, 2002.
  22. Pearson K. On lines and planes of closest fit to systems of points in space. Philosophical Magazine. 1901;2:559–572.
  23. Lee J. Relationships between Properties of Pulp-Fibre and Paper. PhD Diss, University of Toronto, 1992.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».