Summary Conclusions: 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 a₁,..., am â Rn. This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. Its structure makes...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | en_US |
| Published: |
2003
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/3896 |
| _version_ | 1811090591604277248 |
|---|---|
| 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 a₁,..., am â 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-23T14:48:38Z |
| format | Article |
| id | mit-1721.1/3896 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:48:38Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | mit-1721.1/38962019-04-12T08:36:43Z Summary Conclusions: 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 robust statistics clustering analysis We present a practical algorithm for computing the minimum volume n-dimensional ellipsoid that must contain m given points a₁,..., am â 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. Singapore-MIT Alliance (SMA) 2003-12-14T23:22:42Z 2003-12-14T23:22:42Z 2004-01 Article http://hdl.handle.net/1721.1/3896 en_US High Performance Computation for Engineered Systems (HPCES); 192207 bytes application/pdf application/pdf |
| spellingShingle | ellipsoid Newton’s method interior-point method barrier method active set semidefinite program data mining robust statistics clustering analysis Sun, Peng Freund, Robert M. Summary Conclusions: Computation of Minimum Volume Covering Ellipsoids* |
| title | Summary Conclusions: Computation of Minimum Volume Covering Ellipsoids* |
| title_full | Summary Conclusions: Computation of Minimum Volume Covering Ellipsoids* |
| title_fullStr | Summary Conclusions: Computation of Minimum Volume Covering Ellipsoids* |
| title_full_unstemmed | Summary Conclusions: Computation of Minimum Volume Covering Ellipsoids* |
| title_short | Summary Conclusions: Computation of Minimum Volume Covering Ellipsoids* |
| title_sort | summary conclusions computation of minimum volume covering ellipsoids |
| topic | ellipsoid Newton’s method interior-point method barrier method active set semidefinite program data mining robust statistics clustering analysis |
| url | http://hdl.handle.net/1721.1/3896 |
| work_keys_str_mv | AT sunpeng summaryconclusionscomputationofminimumvolumecoveringellipsoids AT freundrobertm summaryconclusionscomputationofminimumvolumecoveringellipsoids |