{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/109355"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/109355","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Computing minimum-volume enclosing ellipsoids","abstract":"A Minimum-Volume Enclosing Ellipsoid (MVEE) is a useful tool for summarizing or representing a large, multidimensional data set (point cloud) by a convex body. MVEEs find applications in areas as diverse as computational geometry, data analysis, and optimal design. The cost of an iterative optimization algorithm for computing an MVEE depends on the size of the problem (dimension of the data and number of points), the convergence rate of the algorithm, the cost per iteration, and the quality of the starting guess. For very large problems, the current state of the art favors low-order methods such as coordinate ascent, despite their often exceedingly slow (linear or sublinear) convergence rates, because of their low cost per iteration. In this work we demonstrate that by carefully exploiting problem structure, higher-order (Newton-like) methods with superlinear convergence rates can also scale to very large problems. A hybrid method that combines the benefits of both the low-order and higher-order methods is also introduced. We also propose new initialization schemes and compare them with existing ones. Additionally, we observe that the computational cost also depends on the distribution of the data, and we show that a standard statistical measure, kurtosis, serves as an excellent indicator of problem difficulty and provides useful guidance in choosing an appropriate solution algorithm and initialization.","abstract_html":"A Minimum-Volume Enclosing Ellipsoid (MVEE) is a useful tool for summarizing or representing a large, multidimensional data set (point cloud) by a convex body. MVEEs find applications in areas as diverse as computational geometry, data analysis, and optimal design. The cost of an iterative optimization algorithm for computing an MVEE depends on the size of the problem (dimension of the data and number of points), the convergence rate of the algorithm, the cost per iteration, and the quality of the starting guess. For very large problems, the current state of the art favors low-order methods such as coordinate ascent, despite their often exceedingly slow (linear or sublinear) convergence rates, because of their low cost per iteration. In this work we demonstrate that by carefully exploiting problem structure, higher-order (Newton-like) methods with superlinear convergence rates can also scale to very large problems. A hybrid method that combines the benefits of both the low-order and higher-order methods is also introduced. We also propose new initialization schemes and compare them with existing ones. Additionally, we observe that the computational cost also depends on the distribution of the data, and we show that a standard statistical measure, kurtosis, serves as an excellent indicator of problem difficulty and provides useful guidance in choosing an appropriate solution algorithm and initialization.","abstract_has_math":false,"creators":["Bowman, Nathaniel Lee"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Heath, Michael","Fischer, Paul","Jacobson, Sheldon","Wright, Stephen"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-03-05T21:36:55Z","date_published":"2021-03-05T21:36:55Z","updated_at":"2026-07-22T22:24:50Z","subjects":["Löwner ellipsoids","core sets","minimum-volume ellipsoids","approximation algorithms"],"languages":["en"],"rights":["Copyright 2020 Nathaniel Bowman"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/109355","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Heath, Michael","Fischer, Paul","Jacobson, Sheldon","Wright, Stephen"]},{"key":"dc:creator","label":"Author","values":["Bowman, Nathaniel Lee"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-03-05T21:36:55Z","2020-11-10","2020-12"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Löwner ellipsoids","core sets","minimum-volume ellipsoids","approximation algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Nathaniel Bowman"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/109355"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["A Minimum-Volume Enclosing Ellipsoid (MVEE) is a useful tool for summarizing or representing a large, multidimensional data set (point cloud) by a convex body. MVEEs find applications in areas as diverse as computational geometry, data analysis, and optimal design. The cost of an iterative optimization algorithm for computing an MVEE depends on the size of the problem (dimension of the data and number of points), the convergence rate of the algorithm, the cost per iteration, and the quality of the starting guess. For very large problems, the current state of the art favors low-order methods such as coordinate ascent, despite their often exceedingly slow (linear or sublinear) convergence rates, because of their low cost per iteration. In this work we demonstrate that by carefully exploiting problem structure, higher-order (Newton-like) methods with superlinear convergence rates can also scale to very large problems. A hybrid method that combines the benefits of both the low-order and higher-order methods is also introduced. We also propose new initialization schemes and compare them with existing ones. Additionally, we observe that the computational cost also depends on the distribution of the data, and we show that a standard statistical measure, kurtosis, serves as an excellent indicator of problem difficulty and provides useful guidance in choosing an appropriate solution algorithm and initialization.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-03-04 without embargo terms","The student, Nathaniel Bowman, accepted the attached license on 2020-11-09 at 15:43.","The student, Nathaniel Bowman, submitted this Dissertation for approval on 2020-11-09 at 16:08.","This Dissertation was approved for publication on 2020-11-10 at 09:25.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15865 on 2021-03-04 at 15:34:23","Made available in DSpace on 2021-03-05T21:36:55Z (GMT). No. of bitstreams: 2 BOWMAN-DISSERTATION-2020.pdf: 3868555 bytes, checksum: a87f53b657fd3e2d9edf4d8d9029be21 (MD5) LICENSE.txt: 4213 bytes, checksum: a64e4ed8f27cd477521488ae53da7df6 (MD5) Previous issue date: 2020-11-10"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Computing minimum-volume enclosing ellipsoids"]}]}],"canonical_facts":{"dc:contributor":["Heath, Michael","Fischer, Paul","Jacobson, Sheldon","Wright, Stephen"],"dc:creator":["Bowman, Nathaniel Lee"],"dc:date":["2021-03-05T21:36:55Z","2020-11-10","2020-12"],"dc:description":["A Minimum-Volume Enclosing Ellipsoid (MVEE) is a useful tool for summarizing or representing a large, multidimensional data set (point cloud) by a convex body. MVEEs find applications in areas as diverse as computational geometry, data analysis, and optimal design. The cost of an iterative optimization algorithm for computing an MVEE depends on the size of the problem (dimension of the data and number of points), the convergence rate of the algorithm, the cost per iteration, and the quality of the starting guess. For very large problems, the current state of the art favors low-order methods such as coordinate ascent, despite their often exceedingly slow (linear or sublinear) convergence rates, because of their low cost per iteration. In this work we demonstrate that by carefully exploiting problem structure, higher-order (Newton-like) methods with superlinear convergence rates can also scale to very large problems. A hybrid method that combines the benefits of both the low-order and higher-order methods is also introduced. We also propose new initialization schemes and compare them with existing ones. Additionally, we observe that the computational cost also depends on the distribution of the data, and we show that a standard statistical measure, kurtosis, serves as an excellent indicator of problem difficulty and provides useful guidance in choosing an appropriate solution algorithm and initialization.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-03-04 without embargo terms","The student, Nathaniel Bowman, accepted the attached license on 2020-11-09 at 15:43.","The student, Nathaniel Bowman, submitted this Dissertation for approval on 2020-11-09 at 16:08.","This Dissertation was approved for publication on 2020-11-10 at 09:25.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15865 on 2021-03-04 at 15:34:23","Made available in DSpace on 2021-03-05T21:36:55Z (GMT). No. of bitstreams: 2 BOWMAN-DISSERTATION-2020.pdf: 3868555 bytes, checksum: a87f53b657fd3e2d9edf4d8d9029be21 (MD5) LICENSE.txt: 4213 bytes, checksum: a64e4ed8f27cd477521488ae53da7df6 (MD5) Previous issue date: 2020-11-10"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/109355"],"dc:language":["en"],"dc:rights":["Copyright 2020 Nathaniel Bowman"],"dc:subject":["Löwner ellipsoids","core sets","minimum-volume ellipsoids","approximation algorithms"],"dc:title":["Computing minimum-volume enclosing ellipsoids"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:50Z"}