Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem
The analysis of incomplete data is a long-standing challenge in practical statistics. When, as is typical, data objects are represented by points in R(d) supercript stop, incomplete data objects correspond to affine subspaces (lines or Delta-flats). With this motivation we study the problem of finding the minimum intersection radius r(L) of a set of lines or Delta-flats L: the least r such that there is a ball of radius r intersecting every flat in L. 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 L of Delta-dimensional convex sets in a Hilbert space, there exist Delta+2 sets L' subset of L such that r(L) <= 2r (L'). Based upon this we present an algorithm that computes a (1+epsilon)-core set L' subset of L, |L'| = O(Delta(4/)epsilon), such that the ball centered at a point c with radius (1+epsilon)r(L') intersects every element of L. The running time of the algorithm is O(n(Delta+1)d poly(Delta/epsilon)). For the case of lines or line segments (Delta = 1), the ( expected) running time of the algorithm can be improved to O(nd poly(1/epsilon)). 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.
incomplete data helly theorem clustering core set k-center approximation inference