Files in this item



application/pdfBOWMAN-DISSERTATION-2020.pdf (4MB)
(no description provided)PDF


Title:Computing minimum-volume enclosing ellipsoids
Author(s):Bowman, Nathaniel Lee
Director of Research:Heath, Michael
Doctoral Committee Chair(s):Heath, Michael
Doctoral Committee Member(s):Fischer, Paul; Jacobson, Sheldon; Wright, Stephen
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(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.
Issue Date:2020-11-10
Rights Information:Copyright 2020 Nathaniel Bowman
Date Available in IDEALS:2021-03-05
Date Deposited:2020-12

This item appears in the following Collection(s)

Item Statistics