CS Events

Qualifying Exam

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


Download as iCal file

Tuesday, April 30, 2019, 01:00pm



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.

Speaker: Yikai Zhang

Location : CoRE B (305)


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

Event Type: Qualifying Exam


Dept. of Computer Science