高维中的凸包，找到多面体的顶点

假设我有一个 6 维空间中的点云，我可以根据需要使其密集。这些点位于低维多面体的表面上（即点向量 (x1, x2, ... x6) 看起来是共面的）。

我想找到这个未知多面体的顶点，我当前的尝试通过 Python 中的 scipy 接口使用 qhull 算法。一开始我只会收到错误消息，显然是由较低维度的输入和/或许多退化点引起的。我尝试了几种蛮力方法来消除退化点，但不是很成功，所以最后，我认为所有这些点都必须位于凸包上。

这个问题 https://stackoverflow.com/questions/26408110/why-does-qhull-error-when-computing-convex-hull-of-a-few-points非常有帮助，因为它建议通过主成分分析进行降维。如果我将点投影到 4D 超平面，qhull 算法运行时不会出现错误（对于任何更高的维度，它不会运行）。

from scipy.spatial import ConvexHull
from sklearn.decomposition import PCA

model = PCA(n_components=4).fit(initial_points)
proj_points = model.transform(initial_points)
hull = ConvexHull(proj_points, qhull_options = "Qx")

上述问题的答案提到，在计算投影点的凸包后，需要将单纯形转换回来。但是 qhull 输出仅包含索引，为什么这些与初始点的索引不匹配？

现在我的问题是我不知道使用哪种精度来实际获得正确的顶点。无论我使点云有多密集，获得的顶点都会因不同的精度而不同。例如，对于 (10000, 6) 数组中的初始点，我得到（其中 E0.03 是该方法有效的最大值）：

hull1 = ConvexHull(proj_points, qhull_options = "Qx, E0.03")
print len(hull1.vertices)
print hull1.vertices

5
[ 437 2116 3978 7519 9381]

并在轴 0,1,2 的一些（信息量不是很大的）投影中绘制它（其中蓝点代表初始点云的选择）：

But for a higher precision (of course) I get a different set:

hull2 = ConvexHull(proj_points, qhull_options = "Qx, E0.003")
print len(hull2.vertices)
print hull2.vertices

29
[  74   75  436  437  756 1117 2116 2366 2618 2937 3297 3615 3616 3978 3979
 4340 4561 4657 4659 4924 5338 5797 6336 7519 7882 8200 9381 9427 9470]

相同的投影（只是角度略有不同）：

我怀疑第一张图片没有足够的顶点，而第二张图片可能有太多顶点。当然，我无法从这些图中提取严格的信息。但是有没有一种好的方法可以找出要使用的精度呢？或者也许是解决这个问题的完全不同的方法（我已经尝试了一些）？

在这个答案中，我假设您已经使用 PCA 将数据近乎无损地压缩为 4 维数据，其中减少的数据位于概念上很少面的 4 维多面体中。我将描述一种解决该多面体面的方法，这反过来会给您顶点。

Let x_i in R⁴, i = 1, ..., m, be the PCA-reduced data points.

Let F = (a, b) be a face, where a is in R⁴ with a • a = 1 and b is in R.

We define the face loss function L as follows, where λ⁺, λ^- > 0 are parameters you choose. λ⁺ should be a very small positive number. λ^- should be a very large positive number.

L(F) = sum_i(λ⁺ • max(0, a • x_i + b) - λ^- • min(0, a • x_i + b))

We want to find minimal faces F with respect to the loss function L. The small set of all minimal faces will describe your polytope. You can solve for minimal faces by randomly initializing F and then performing gradient descent using the partial derivatives ∂L / ∂a_j, j = 1, 2, 3, 4, and ∂L / ∂b. At each step of gradient descent, constrain a • a to be 1 by normalizing.

∂L / ∂a_j = sum_i(λ⁺ &bullet; x_j &bullet; [a &bullet; x_i + b > 0] - λ^- &bullet; x_j &bullet; [a &bullet; x_i + b < 0]) for j = 1, 2, 3, 4

∂L / ∂b = sum_i(λ⁺ &bullet; [a &bullet; x_i + b > 0] - λ^- &bullet; [a &bullet; x_i + b < 0])

Note 艾弗森括号 http://en.wikipedia.org/wiki/Iverson_bracket：如果 P 为真，则 [P] = 1；如果 P 为假，则 [P] = 0。