Text

theses

ETD doctoral

The Convex Hull Membership (CHM) problem queries whether a point p in m-dimensional Euclidean space lies in the convex hull of a compact subset S in that Euclidean space. For S finite, CHM forms a basic problem in Computational Geometry and Linear Programming. It also serves as a query problem in many applications e.g. Topic Modeling, Non-negative Matrix Factorization. The Triangle Algorithm (TA) invented by Dr. Kalantari is a novel algorithm for CHM, first developed for the case where S is finite and subsequently for the more general case where S is any compact subset. The TA either computes an approximate solution or proves p lies outside of conv(S) by computing a separating hyperplane. The number of iterations of TA to solve CHM is independent of the dimension m and it thus can serve as an efficient oracle in large scale and high dimensional cases of CHM. In this dissertation we mainly investigate the computational aspects of solving three problems via the Triangle Algorithm, as stated below:

1) Irredundancy problem: We investigate the problem of computing all or a good approximation of vertices of a convex hull given a set of n points in dimension m, known as the irredundancy problem. This problem becomes challenging as m grows, especially for classical algorithms such as Gift Wrapping and QuickHull due to their exponential running times in terms of the dimension. The All Vertex Triangle Algorithm (AVTA) is proposed to tackle the efficiency issue for the irredundancy problem and its variations. The AVTA leverages on the TA as a membership oracle and progressively recovers vertices of convex hull of S, potentially after the Johnson-Lindenstrauss projection pre-processing. We apply AVTA to design new practical algorithms for two popular machine learning problems: topic modeling and non-negative matrix factorization. Our experimental results show its robustness and efficiency in solving the irredundancy problem and its variations in real world applications.

2) Spherical-CHM: We investigate Spherical-CHM as a special case of CHM where the n points of S lie on a sphere centered at p. The Spherical-CHM is shown to be equivalent to the general case in the sense that the general CHM is reducible to Spherical-CHM. Based on the structure of Spherical-CHM, we propose a novel version of the TA called the Spherical Triangle Algorithm(Spherical-TA) which converts CHM into Spherical-CHM and then applying the TA. Under mild assumptions, it is provably faster than TA. Empirically, we observe that it has better efficiency than TA. We list several applications of the Spherical-TA and empirically show the efficiency of the Spherical-TA as an oracle for CHM query in solving various problems.

3) Solving Linear System: We consider solving a linear system Ax=b, where A is an m by n real or complex matrix of arbitrary rank. We describe a novel geometric algorithm for computing an approximate solution based on Triangle Algorithm for general CHM, where the underlying set S is a compact subset of a Euclidean space. The corresponding Triangle Algorithm is applicable to linear systems of arbitrary dimension, requiring no assumption on the matrix A. When A is invertible, the algorithm approximates the unique solution. When A is not invertible but Ax=b is solvable, it is able to approximate the solution with smallest norm, and when Ax=b has no solution, it is able to approximate the solution that minimizes ||Ax – b|| with smallest norm and computes a certificate proving unsolvability. Empirically we compare the algorithm with two popular linear system solvers BiCGSTAB and GMRES with iLU-preconditioner. We consider the case where A is a square matrix and observe superior efficiency of our proposed algorithm in approximating the solution or proving unsolvability.

ETD_11352

Ph.D.

Includes bibliographical references

doi:10.7282/t3-myft-hy83

The author owns the copyright to this work.