Skip to content Skip to navigation
Qualifying Exam
4/30/2019 01:00 pm
CoRE B (305)

Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries in Machine Learning and Computational Geometry Applications

Yikai Zhang, Dept. of Computer Science

Examination Committee: Prof. Bahman Kalantari (Chair), Prof. Pranjal Awasthi, Prof. William Steiger, Prof. Mridul Aanjaneya

Abstract

The Convex Hull Membership (CHM) problem is testing if a given m-dimensional vector lies in the convex hull of a finite point set. CHM is a fundamental problem in Linear Programming, Machine Learning and Computational Geometry. The Triangle Algorithm, proposed by Bahman Kalantari is a dimension free algorithm which either computes an approximate solution or provides a separating hyperplane.  Leveraging on the Triangle Algorithm, we have designed a fast algorithm called All Vertex Triangle Algorithm (AVTA) for the irredundancy problem, i.e. the problem of computing all, or a good subset of the vertices of the convex hull of a finite point set in high dimensions. More Importantly, AVTA is also applicable under perturbations of data, thus a robust algorithm. We have applied AVTA to design new practical algorithms for topic models and non-negative matrix factorization problems, two high dimensional problems in machine learning. For topic models the AVTA-based algorithm leads to significantly better reconstruction of the topic-word matrix than state of the art approaches.  For non-negative matrix factorization AVTA is competitive with existing methods that are specialized for this task. In addition, based on a new version of Triangle Algorithm called Spherical Triangle Algorithm we achieve further improvement of AVTA. In summary, the Triangle Algorithm has proven to be a very effective oracle with diverse applications. We have developed and released the source code for these algorithms. We believe the developed tools find many other applications in distinct areas of computer science and optimization.