Computing minimum-volume enclosing ellipsoids

Bowman, Nathaniel Lee

Permalink

https://hdl.handle.net/2142/109355 Copy

Description

Title

Computing minimum-volume enclosing ellipsoids

Author(s)

Bowman, Nathaniel Lee

Issue Date

2020-11-10

Director of Research (if dissertation) or Advisor (if thesis)

Heath, Michael

Doctoral Committee Chair(s)

Heath, Michael

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

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.

Graduation Semester

2020-12

Type of Resource

Thesis

Permalink

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

Copyright and License Information

Copyright 2020 Nathaniel Bowman

Owning Collections