Robust Vertex Enumeration for Convex Hulls in High Dimensions
share
Computation of the vertices of the convex hull of a set S of n points in R ^m is a fundamental problem in computational geometry, optimization, machine learning and more. We present "All Vertex Triangle Algorithm" (AVTA), a robust and efficient algorithm for computing the subset S of all K vertices of conv(S), the convex hull of S. If Γ_* is the minimum of the distances from each vertex to the convex hull of the remaining vertices, given any γ≤γ_* = Γ_*/R, R the diameter of S, AVTA computes S in O(nK(m+ γ^-2)) operations. If γ_* is unknown but K is known, AVTA computes S in O(nK(m+ γ_*^-2)) (γ_*^-1) operations. More generally, given t ∈ (0,1), AVTA computes a subset S^t of S in O(n | S^t|(m+ t^-2)) operations, where the distance between any p ∈ conv(S) to conv( S^t) is at most t R. Next we consider AVTA where input is S_ε, an ε perturbation of S. Assuming a bound on ε in terms of the minimum of the distances of vertices of conv(S) to the convex hull of the remaining point of S, we derive analogous complexity bounds for computing S_ε. We also analyze AVTA under random projections of S or S_ε. Finally, via AVTA we design new practical algorithms for two popular machine learning problems: topic modeling and non-negative matrix factorization. For topic models AVTA leads to significantly better reconstruction of the topic-word matrix than state of the art approaches arora2013practical, bansal2014provable. For non-negative matrix AVTA is competitive with existing methods arora2012computing. Empirically AVTA is robust and can handle larger amounts of noise than existing methods.
READ FULL TEXT