Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem
Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem
复制标题
不完整数据分析和内在维度 Helly 定理
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
L. Schulman
中科院分区：
文献类型：
--
作者：
Jie Gao;M. Langberg;L. Schulman
不完整数据的分析是实际统计中长期存在的挑战。通常，当数据对象由 ℝd 中的点表示时，不完整的数据对象对应于仿射子空间（线或 Δ 平面）。出于这个动机，我们研究了寻找一组线或 Δ-平面 ℒ 的最小相交半径r(ℒ) 的问题：最小的 r 使得存在一个半径为 r 的球与 ℒ 中的每个平面相交。用于查找点集的最小包围球（或由多个球聚类）的已知算法不容易扩展到更高维的平面，主要是因为平面之间的“距离”不满足三角形不等式。在本文中，我们展示了如何通过海利定理的新模拟来恢复问题的几何形状（即三角不等式的替代）。这个“内在维度”Helly 定理指出：对于希尔伯特空间中任何 Δ 维凸集族 ℒ，都存在 Δ+2 个集合 ℒ′⊆ℒ，使得 r(ℒ)≤2r(ℒ′)。基于此，我们提出了一种算法，计算 (1+ε) 核心集ℒ′⊆ℒ，|ℒ′|=O(Δ4/ε)，使得以点 c 为中心、半径为 (1+ε)r(ℒ′) 的球与ℒ的每个元素相交。该算法的运行时间为O(nΔ+1dpoly (Δ/ε))。对于直线或线段（Δ=1）的情况，算法的（预期）运行时间可以提高到O(ndpoly (1/ε))。我们注意到，核心集的大小仅取决于输入对象的维度，并且与输入大小 n 和环境空间的维度 d 无关。
The analysis of incomplete data is a long-standing challenge in practical statistics. When, as is typical, data objects are represented by points in ℝd, incomplete data objects correspond to affine subspaces (lines or Δ-flats). With this motivation we study the problem of finding the minimum intersection radiusr(ℒ) of a set of lines or Δ-flats ℒ: the least r such that there is a ball of radius r intersecting every flat in ℒ. Known algorithms for finding the minimum enclosing ball for a point set (or clustering by several balls) do not easily extend to higher-dimensional flats, primarily because “distances” between flats do not satisfy the triangle inequality. In this paper we show how to restore geometry (i.e., a substitute for the triangle inequality) to the problem, through a new analog of Helly’s theorem. This “intrinsic-dimension” Helly theorem states: for any family ℒ of Δ-dimensional convex sets in a Hilbert space, there exist Δ+2 sets ℒ′⊆ℒ such that r(ℒ)≤2r(ℒ′). Based upon this we present an algorithm that computes a (1+ε)-core set ℒ′⊆ℒ, |ℒ′|=O(Δ4/ε), such that the ball centered at a point c with radius (1+ε)r(ℒ′) intersects every element of ℒ. The running time of the algorithm is O(nΔ+1dpoly (Δ/ε)). For the case of lines or line segments (Δ=1), the (expected) running time of the algorithm can be improved to O(ndpoly (1/ε)). We note that the size of the core set depends only on the dimension of the input objects and is independent of the input size n and the dimension d of the ambient space.