Robust vertex enumeration for convex hulls in high dimensions

Pranjal Awasthi, Bahman Kalantari, Yikai Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

The problem of computing the vertices of the convex hull of a given input set S= { vi∈ Rm: i= 1 , ⋯ , n} is a classic and fundamental problem, studied in the context of computational geometry, linear and convex programming, machine learning and more. In this article we present All Vertex Triangle Algorithm (AVTA), a robust and efficient algorithm for this problem. On the one hand, without any assumptions, AVTA computes approximation to the subset S¯ of all K vertices of the convex hull of S so that the convex hull of the approximate subset of vertices is as close to conv(S) as desired. On the other hand, assuming a known lower bound γ on the ratio Γ/ R, where Γ the minimum of the distances from each vertex to the convex hull of the remaining vertices and R the diameter of S, AVTA can recover all of S¯. Furthermore, assuming that instead of S the input is an ε-perturbation of S, S¯ ε, where ‖vi-viε‖≤εR, AVTA can compute approximation to conv(S¯ ε) , to any prescribed accuracy. Also, given a lower bound to the ratio Σ/ R, where Σ is the minimum of the distances from each vertex to the convex hull of the remaining point of S, AVTA can recover all of S¯ ε. We show Σ≥ ρΓ/ R, where ρ is the minimum distance between distinct pair of points in S and prove the following main results: (1)Given any t∈ (0 , 1) , AVTA computes a subset S¯ t of S¯ of cardinality K( t ) in O(nK( t )(m+ t- 2)) operations so that for any p∈ conv(S) its Euclidean distance to conv(S¯ t) is at most tR.(2)Given γ≤ γ= Γ/ R, AVTA computes S¯ in O(nK(m+ γ- 2)) operations.(3)If K is known, the complexity of AVTA is O(nK(m+γ∗-2)log(γ∗-1)). Assuming instead of S, its ε-perturbation, Sε is given, we prove (i)Given any t∈ (0 , 1) , AVTA computes a subset S¯εt⊂S¯ε of cardinality Kε(t) in O(nKε(t)(m+t-2)) operations so that for any p∈ conv(S) its distance to conv(S¯εt) is at most (t+ ε) R.(ii)Given σ∈ [4 ε, σ= Γ/ R] , AVTA computes S¯ ε in O(nKε(m+ σ- 2)) operations, where K≤ Kε≤ n.(iii)If γ≤ γ= Γ/ R is known satisfying 4 ε≤ γρ/ R, AVTA computes S¯ ε in O(nKε(m+(γρ∗)-2)) operations.(iv)Given σ∈ [4 ε, σ] , if K is known, AVTA computes S¯ ε in O(nK(m+σ∗-2)log(σ∗-1)) operations. We also consider the application of AVTA in the recovery of vertices through the projection of S or Sε under a Johnson–Lindenstrauss randomized linear projection L:Rm→Rm′. Denoting U= L(S) and Uε= L(Sε) , by relating the robustness parameters of conv(U) and conv(Uε) to those of conv(S) and conv(Sε) , we derive analogous complexity bounds for probabilistic computation of the vertex set of conv(U) or those of conv(Uε) , or an approximation to them. Finally, we apply AVTA to design new practical algorithms for two popular machine learning problems: topic modeling and non-negative matrix factorization. For topic models, our new algorithm leads to significantly better reconstruction of the topic-word matrix than state of the art approaches of Arora et al. (International conference on machine learning, pp 280–288, 2013) and Bansal et al. (Advances in neural information processing systems, pp 1997–2005, 2014). Additionally, we provide a robust analysis of AVTA and empirically demonstrate that it can handle larger amounts of noise than existing methods. For non-negative matrix factorization we show that AVTA is competitive with existing methods that are specialized for this task in Arora et al. (Proceedings of the forty-fourth annual ACM symposium on theory of computing, ACM, pp 145–162, 2012a). We also contrast AVTA with Blum et al. (Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, Society for Industrial and Applied Mathematics, pp 548–557, 2016) Greedy Clustering coreset algorithm for computing approximation to the set of vertices and argue that not only there are regimes where AVTA outperforms that algorithm but it can also be used as a pre-processing step to their algorithm. Thus the two algorithms in fact complement each other.

Original languageEnglish (US)
JournalAnnals of Operations Research
DOIs
StateAccepted/In press - Jan 1 2020

All Science Journal Classification (ASJC) codes

  • Decision Sciences(all)
  • Management Science and Operations Research

Keywords

  • Approximation algorithms
  • Convex hull membership
  • Linear programming
  • Machine learning
  • Random projections

Fingerprint Dive into the research topics of 'Robust vertex enumeration for convex hulls in high dimensions'. Together they form a unique fingerprint.

Cite this