Computation of Minimum Volume Covering Ellipsoids
We present a practical algorithm for computing the minimum volume n-dimensional ellipsoid that must contain m given points al,...,am C Rn . This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. Its structure makes it...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/5090 |
| _version_ | 1826207424342654976 |
|---|---|
| author | Sun, Peng Freund, Robert M. |
| author_facet | Sun, Peng Freund, Robert M. |
| author_sort | Sun, Peng |
| collection | MIT |
| description | We present a practical algorithm for computing the minimum volume n-dimensional ellipsoid that must contain m given points al,...,am C Rn . 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. |
| first_indexed | 2024-09-23T13:49:26Z |
| format | Working Paper |
| id | mit-1721.1/5090 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:49:26Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/50902019-04-12T08:15:28Z Computation of Minimum Volume Covering Ellipsoids Sun, Peng Freund, Robert M. Ellipsoid, Newton's method, interior-point method, barrier method, active set, semidefinite program, data mining. We present a practical algorithm for computing the minimum volume n-dimensional ellipsoid that must contain m given points al,...,am C Rn . 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. 2004-05-28T19:22:45Z 2004-05-28T19:22:45Z 2002-07 Working Paper http://hdl.handle.net/1721.1/5090 en_US Operations Research Center Working Paper;OR 364-02 1786129 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Ellipsoid, Newton's method, interior-point method, barrier method, active set, semidefinite program, data mining. Sun, Peng Freund, Robert M. Computation of Minimum Volume Covering Ellipsoids |
| title | Computation of Minimum Volume Covering Ellipsoids |
| title_full | Computation of Minimum Volume Covering Ellipsoids |
| title_fullStr | Computation of Minimum Volume Covering Ellipsoids |
| title_full_unstemmed | Computation of Minimum Volume Covering Ellipsoids |
| title_short | Computation of Minimum Volume Covering Ellipsoids |
| title_sort | computation of minimum volume covering ellipsoids |
| topic | Ellipsoid, Newton's method, interior-point method, barrier method, active set, semidefinite program, data mining. |
| url | http://hdl.handle.net/1721.1/5090 |
| work_keys_str_mv | AT sunpeng computationofminimumvolumecoveringellipsoids AT freundrobertm computationofminimumvolumecoveringellipsoids |