CS Events Monthly View
PhD DefenseComputational Aspects of the Triangle Algorithm for Convex Hull Membership  a Universal Geometric Problem 


Thursday, December 10, 2020, 12:00pm  02:00pm 

Speaker: Yikai Zhang
Location : Remote via Webex
Committee:
Prof. Bahman Kalantari (Chair)
Prof. Sepehr Assadi
Prof. Abdeslam Boularias
Prof. Min Xu (Outside Member, Statistics Department, Rutgers)
Event Type: PhD Defense
Abstract: The Convex Hull Membership (CHM) problem queries whether a point p in mdimensional 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, Nonnegative 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 JohnsonLindenstrauss projection preprocessing. We apply AVTA to design new practical algorithms for two popular machine learning problems: topic modeling and nonnegative matrix factorization. Our experimental results show its robustness and efficiency in solving the irredundancy problem and its variations in real world applications.2) SphericalCHM: We investigate SphericalCHM as a special case of CHM where the n points of S lie on a sphere centered at p. The SphericalCHM is shown to be equivalent to the general case in the sense that the general CHM is reducible to SphericalCHM. Based on the structure of SphericalCHM, we propose a novel version of the TA called the Spherical Triangle Algorithm(SphericalTA) which converts CHM into SphericalCHM 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 SphericalTA and empirically show the efficiency of the SphericalTA 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 Kalantari’s 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 iLUpreconditioner. 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.
: