Computation of minimum-volume covering ellipsoids
Publication
, Journal Article
Sun, P; Freund, RM
Published in: Operations Research
September 1, 2004
We present a practical algorithm for computing the minimum-volume n-dimensional ellipsoid that must contain m given points a I, a m ε R n. This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. Its structure makes it particularly amenable to solution by interior-point methods, and it has been the subject of much theoretical complexity analysis. Here we focus on computation. We present a combined interior-point and active-set method for solving this problem. Our computational results demonstrate that our method solves very large problem instances (m = 30,000 and n = 30) to a high degree of accuracy in under 30 seconds on a personal computer.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
Operations Research
DOI
ISSN
0030-364X
Publication Date
September 1, 2004
Volume
52
Issue
5
Start / End Page
690 / 706
Related Subject Headings
- Operations Research
- 3507 Strategy, management and organisational behaviour
- 1503 Business and Management
- 0802 Computation Theory and Mathematics
- 0102 Applied Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Sun, P., & Freund, R. M. (2004). Computation of minimum-volume covering ellipsoids. Operations Research, 52(5), 690–706. https://doi.org/10.1287/opre.1040.0115
Sun, P., and R. M. Freund. “Computation of minimum-volume covering ellipsoids.” Operations Research 52, no. 5 (September 1, 2004): 690–706. https://doi.org/10.1287/opre.1040.0115.
Sun P, Freund RM. Computation of minimum-volume covering ellipsoids. Operations Research. 2004 Sep 1;52(5):690–706.
Sun, P., and R. M. Freund. “Computation of minimum-volume covering ellipsoids.” Operations Research, vol. 52, no. 5, Sept. 2004, pp. 690–706. Scopus, doi:10.1287/opre.1040.0115.
Sun P, Freund RM. Computation of minimum-volume covering ellipsoids. Operations Research. 2004 Sep 1;52(5):690–706.
Published In
Operations Research
DOI
ISSN
0030-364X
Publication Date
September 1, 2004
Volume
52
Issue
5
Start / End Page
690 / 706
Related Subject Headings
- Operations Research
- 3507 Strategy, management and organisational behaviour
- 1503 Business and Management
- 0802 Computation Theory and Mathematics
- 0102 Applied Mathematics