Computing minimum-volume enclosing ellipsoids

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2021

Author dc:creator

• Bowman, Nathaniel Lee

Contributors dc:contributor

• Heath, Michael
• Fischer, Paul
• Jacobson, Sheldon
• Wright, Stephen

• Löwner ellipsoids
• core sets
• minimum-volume ellipsoids
• approximation algorithms

Statement dc:rights

• Copyright 2020 Nathaniel Bowman

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/109355

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/109355