55015

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Пленарный доклад

Название: 

Minimum-size ellipsoids enclosing a subset of points: Heuristics and experiments with algorithms

Наименование конференции: 

  • 2nd International Symposium of New Techniques in Medical Diagnosis and Treatment (Wuhan, China, 2019)

Наименование источника: 

  • Preprints of the 2nd International Symposium of New Techniques in Medical Diagnosis and Treatment (Wuhan, China, 2019)

Город: 

  • Wuhan

Издательство: 

  • Huazhong University of Science and Technology

Год издания: 

2019

Страницы: 

21 (1-21)
Аннотация
In many areas of system theory such as estimation, filtering, data mining, decision making, image reconstruction, etc., it is often the case that the available data is excessive, while the capacity of the storage is limited, so that some of the observation data is to be dis-carded without an essential loss of useful information. We discuss a very simple model for-mulation that can be thought of being at the core of problems of this sort. Namely, the problem is: Discard M out of the N given points in n-dimensional space in such a way that the ellipsoid around the remaining ones be smallest in size. The understanding is that the number of dis-carded points is much smaller than the total amount of points. This setup captures for instance the case where noise-corrupted observations containing outliers from a certain distribution class are available, and are to be filtered out. For example, the points are known to be generated from a Gaussian distribution with unknown mean and covariance and contain low-level noise and small number of outliers; the goal is to recover the underlying Gaussian distribution. This prospective formulation motivates use of ellipsoids as enclosing sets, thus linking the problem to finding high probability confidence ellipsoids explaining the available data. As formulated, the problem is generically combinatorial, and we propose several suboptimal approaches to the solution with reasonable computational effort. These algorithms are based on either common sense reasonings or certain efficient heuristics; they are then tested numerically over sets of randomly generated data. For small values of M and N, the exact solution of the prob-lem can be found by ``brute force’’ and then compared to the outcome of the proposed algo-rithms.

Библиографическая ссылка: 

Щербаков П.С. Minimum-size ellipsoids enclosing a subset of points: Heuristics and experiments with algorithms / Preprints of the 2nd International Symposium of New Techniques in Medical Diagnosis and Treatment (Wuhan, China, 2019). Wuhan: Huazhong University of Science and Technology, 2019. С. 21 (1-21).