Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries
share
The it Convex Hull Membership(CHM) problem is: Given a point p and a subset S of n points in R^m, is p ∈ conv(S)? CHM is not only a fundamental problem in Linear Programming, Computational Geometry, Machine Learning and Statistics, it also serves as a query problem in many applications e.g. Topic Modeling, LP Feasibility, Data Reduction. The Triangle Algorithm (TA) kalantari2015characterization either computes an approximate solution in the convex hull, or a separating hyperplane. The Spherical-CHM is a CHM, where p=0 and each point in S has unit norm. First, we prove the equivalence of exact and approximate versions of CHM and Spherical-CHM. On the one hand, this makes it possible to state a simple version of the original TA. On the other hand, we prove that under the satisfiability of a simple condition in each iteration, the complexity improves to O(1/ε). The analysis also suggests a strategy for when the property does not hold at an iterate. This suggests the Spherical-TA which first converts a given CHM into a Spherical-CHM before applying the algorithm. Next we introduce a series of applications of Spherical-TA. In particular, Spherical-TA serves as a fast version of vanilla TA to boost its efficiency. As an example, this results in a fast version of AVTAawasthi2018robust, called AVTA^+ for solving exact or approximate irredundancy problem. Computationally, we have considered CHM, LP and Strict LP Feasibility and the Irredundancy problem. Based on substantial amount of computing, Spherical-TA achieves better efficiency than state of the art algorithms. Leveraging on the efficiency of Spherical-TA, we propose AVTA^+ as a pre-processing step for data reduction which arises in such applications as in computing the Minimum Volume Enclosing Ellipsoid moshtagh2005minimum.
READ FULL TEXT