Robust vertex enumeration for convex hulls in high dimensions
- PDF / 1,672,768 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 17 Downloads / 180 Views
Robust vertex enumeration for convex hulls in high dimensions Pranjal Awasthi1 · Bahman Kalantari1 · Yikai Zhang1 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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: t
(1) Given any t ∈ (0, 1), AVTA computes a subset S of S of cardinality K (t) in O(n K (t) (m + t −2 )) operations so that for any p ∈ conv(S) its Euclidean distance t to conv(S ) is at most t R. (2) Given γ ≤ γ∗ = Γ∗ /R, AVTA computes S in O(n K (m + γ −2 )) operations. (3) If K is known, the complexity of AVTA is O(n K (m + γ∗−2 ) log(γ∗−1 )). Assuming instead of S, its ε-perturbation, Sε is given, we prove t
(t)
(i) Given any t ∈ (0, 1), AVTA computes a subset S ε ⊂ S ε of cardinality K ε in t (t) O(n K ε (m + t −2 )) operations so that for any p ∈ conv(S) its distance to conv(S ε ) is at most (t + ε)R. (ii) Given σ ∈ [4ε, σ∗ = Γ∗ /R], AVTA computes S ε in O(n K ε (m + σ −2 )) operations, where K ≤ K ε ≤ n.
A conference version of the article appeared in the Proceedings of AISTATS 2018.
B
Bahman Kalantari [email protected]
Extended author information available on the last page of the article
123
Annals of Operations Research
(iii) If γ ≤ γ∗ = Γ∗ /R is known satisfying 4ε ≤ γρ∗ /R, AV T A computes S ε in O(n K ε (m + (γρ∗ )−2 )) operations. (iv) Given σ ∈ [4ε, σ∗ ], if K is known, AVTA computes S ε in O(n K (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 t
Data Loading...
